<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">
<script>
    (function () {
        if ('') {
            if (prompt('请输入文章密码') !== '') {
                alert('密码错误！');
                if (history.length === 1) {
                    location.replace("https://google.com"); // 这里替换成你的首页
                } else {
                    history.back();
                }
            }
        }
    })();
</script>








<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="算法,">










<meta name="description" content="本文来自laravel-china 二分查找（数组里查找某个元素）12345678910111213function bin_sch($array,  $low, $high, $k)&amp;#123;   if ( $low &amp;lt;= $high)&amp;#123;       $mid =  intval(($low+$high)/2 );       if ($array[$mid] ==  $k)&amp;">
<meta name="keywords" content="算法">
<meta property="og:type" content="article">
<meta property="og:title" content="基本数据结构算法">
<meta property="og:url" content="http://yoursite.com/2018/11/23/基本数据结构算法/index.html">
<meta property="og:site_name" content="苏生不惑的博客">
<meta property="og:description" content="本文来自laravel-china 二分查找（数组里查找某个元素）12345678910111213function bin_sch($array,  $low, $high, $k)&amp;#123;   if ( $low &amp;lt;= $high)&amp;#123;       $mid =  intval(($low+$high)/2 );       if ($array[$mid] ==  $k)&amp;">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2020-04-15T07:30:09.313Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="基本数据结构算法">
<meta name="twitter:description" content="本文来自laravel-china 二分查找（数组里查找某个元素）12345678910111213function bin_sch($array,  $low, $high, $k)&amp;#123;   if ( $low &amp;lt;= $high)&amp;#123;       $mid =  intval(($low+$high)/2 );       if ($array[$mid] ==  $k)&amp;">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2018/11/23/基本数据结构算法/">



<meta name="referrer" content="never"> ​​​​


  <title>基本数据结构算法 | 苏生不惑的博客</title>
  








</head>

<body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">苏生不惑的博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/11/23/基本数据结构算法/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="苏生不惑">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="苏生不惑的博客">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">基本数据结构算法</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-11-23T21:07:18+08:00">
                2018-11-23
              </time>
            

            

            
          </span>

          

          
            
          

          
          

          
            <span class="post-meta-divider">|</span>
            <span class="page-pv"><i class="fa fa-file-o"></i>
            <span class="busuanzi-value" id="busuanzi_value_page_pv"></span>次
            </span>
          

          
            <div class="post-wordcount">
              
                
                  <span class="post-meta-divider">|</span>
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  9.3k 字
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  45 分钟
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>本文来自<a href="https://laravel-china.org/articles/18148" target="_blank" rel="noopener">laravel-china</a></p>
<h3 id="二分查找（数组里查找某个元素）"><a href="#二分查找（数组里查找某个元素）" class="headerlink" title="二分查找（数组里查找某个元素）"></a>二分查找（数组里查找某个元素）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bin_sch</span>(<span class="params">$array,  $low, $high, $k</span>)</span>&#123;   </span><br><span class="line"><span class="keyword">if</span> ( $low &lt;= $high)&#123;   </span><br><span class="line">    $mid =  intval(($low+$high)/<span class="number">2</span> );   </span><br><span class="line">    <span class="keyword">if</span> ($array[$mid] ==  $k)&#123;   </span><br><span class="line">        <span class="keyword">return</span> $mid;   </span><br><span class="line">    &#125;elseif ( $k &lt; $array[$mid])&#123;   </span><br><span class="line">        <span class="keyword">return</span>  bin_sch($array, $low,  $mid<span class="number">-1</span>, $k);   </span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;   </span><br><span class="line">        <span class="keyword">return</span>  bin_sch($array, $mid+ <span class="number">1</span>, $high, $k);   </span><br><span class="line">    &#125;   </span><br><span class="line">&#125;   </span><br><span class="line"><span class="keyword">return</span> <span class="number">-1</span>;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="顺序查找（数组里查找某个元素）"><a href="#顺序查找（数组里查找某个元素）" class="headerlink" title="顺序查找（数组里查找某个元素）"></a>顺序查找（数组里查找某个元素）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span>  <span class="title">seq_sch</span>(<span class="params">$array, $n,  $k</span>)</span>&#123;   </span><br><span class="line">$array[$n] =  $k;   </span><br><span class="line"><span class="keyword">for</span>($i=<span class="number">0</span>;  $i&lt;$n; $i++)&#123;   </span><br><span class="line">    <span class="keyword">if</span>( $array[$i]==$k)&#123;   </span><br><span class="line">        <span class="keyword">break</span>;   </span><br><span class="line">    &#125;   </span><br><span class="line">&#125;   </span><br><span class="line"><span class="keyword">if</span> ($i&lt;$n)&#123;   </span><br><span class="line">    <span class="keyword">return</span>  $i;   </span><br><span class="line">&#125;<span class="keyword">else</span>&#123;   </span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;   </span><br><span class="line">&#125;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="线性表的删除（数组中实现）"><a href="#线性表的删除（数组中实现）" class="headerlink" title="线性表的删除（数组中实现）"></a>线性表的删除（数组中实现）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">delete_array_element</span>(<span class="params">$array , $i</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    $len =  count($array);   </span><br><span class="line">    <span class="keyword">for</span> ($j= $i; $j&lt;$len; $j ++)&#123;  </span><br><span class="line">            $array[$j] = $array [$j+<span class="number">1</span>];  </span><br><span class="line">    &#125;  </span><br><span class="line">    array_pop ($array);  </span><br><span class="line">    <span class="keyword">return</span> $array ;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="冒泡排序（数组排序）"><a href="#冒泡排序（数组排序）" class="headerlink" title="冒泡排序（数组排序）"></a>冒泡排序（数组排序）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bubble_sort</span>(<span class="params"> $array</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    $count = count( $array);  </span><br><span class="line">    <span class="keyword">if</span> ($count &lt;= <span class="number">0</span> ) <span class="keyword">return</span> <span class="literal">false</span>;  </span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span> ; $i&lt;$count; $i ++)&#123;  </span><br><span class="line">            <span class="keyword">for</span>($j=$count<span class="number">-1</span> ; $j&gt;$i; $j--)&#123;  </span><br><span class="line">                    <span class="keyword">if</span> ($array[$j] &lt; $array [$j<span class="number">-1</span>])&#123;  </span><br><span class="line">                             $tmp = $array[$j];  </span><br><span class="line">                             $array[$j] = $array[ $j<span class="number">-1</span>];  </span><br><span class="line">                            $array [$j<span class="number">-1</span>] = $tmp;  </span><br><span class="line">                    &#125;  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $array;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="快速排序（数组排序）"><a href="#快速排序（数组排序）" class="headerlink" title="快速排序（数组排序）"></a>快速排序（数组排序）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">quick_sort</span>(<span class="params">$array </span>) </span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (count($array) &lt;= <span class="number">1</span>) <span class="keyword">return</span>  $array;  </span><br><span class="line">    $key = $array [<span class="number">0</span>];  </span><br><span class="line">    $left_arr  = array();  </span><br><span class="line">    $right_arr = array();  </span><br><span class="line">    <span class="keyword">for</span> ($i= <span class="number">1</span>; $i&lt;count($array ); $i++)&#123;  </span><br><span class="line">            <span class="keyword">if</span> ($array[ $i] &lt;= $key)  </span><br><span class="line">                    $left_arr [] = $array[$i];  </span><br><span class="line">            <span class="keyword">else</span>  </span><br><span class="line">                     $right_arr[] = $array[$i ];  </span><br><span class="line">    &#125;  </span><br><span class="line">    $left_arr = quick_sort($left_arr );  </span><br><span class="line">    $right_arr = quick_sort( $right_arr);  </span><br><span class="line">    <span class="keyword">return</span> array_merge($left_arr , array($key), $right_arr);  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="字符串长度"><a href="#字符串长度" class="headerlink" title="字符串长度"></a>字符串长度</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">strlen</span> (<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> ($str == <span class="string">''</span> ) <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">    $count =  <span class="number">0</span>;  </span><br><span class="line">    <span class="keyword">while</span> (<span class="number">1</span>)&#123;  </span><br><span class="line">            <span class="keyword">if</span> ( $str[$count] != NULL)&#123;  </span><br><span class="line">                     $count++;  </span><br><span class="line">                    <span class="keyword">continue</span>;  </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;  </span><br><span class="line">                    <span class="keyword">break</span>;  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $count;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="截取子串"><a href="#截取子串" class="headerlink" title="截取子串"></a>截取子串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">substr</span>(<span class="params">$str, $start,  $length=NULL</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> ($str== <span class="string">''</span> || $start&gt;strlen($str )) <span class="keyword">return</span>;  </span><br><span class="line">    <span class="keyword">if</span> (($length!=NULL) &amp;&amp; ( $start&gt;<span class="number">0</span>) &amp;&amp; ($length&gt; strlen($str)-$start)) <span class="keyword">return</span>;  </span><br><span class="line">    <span class="keyword">if</span> (( $length!=NULL) &amp;&amp; ($start&lt; <span class="number">0</span>) &amp;&amp; ($length&gt;strlen($str )+$start)) <span class="keyword">return</span>;  </span><br><span class="line">    <span class="keyword">if</span> ($length ==  NULL) $length = (strlen($str ) - $start);  </span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> ($start &lt;  <span class="number">0</span>)&#123;  </span><br><span class="line">            <span class="keyword">for</span> ($i=(strlen( $str)+$start); $i&lt;(strlen ($str)+$start+$length ); $i++) &#123;  </span><br><span class="line">                    $substr .=  $str[$i];  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span> ($length  &gt; <span class="number">0</span>)&#123;  </span><br><span class="line">            <span class="keyword">for</span> ($i= $start; $i&lt;($start+$length ); $i++) &#123;  </span><br><span class="line">                    $substr  .= $str[$i];  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span> ( $length &lt; <span class="number">0</span>)&#123;  </span><br><span class="line">            <span class="keyword">for</span> ($i =$start; $i&lt;(strlen( $str)+$length); $i++) &#123;  </span><br><span class="line">                    $substr .= $str[$i ];  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $substr;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="字符串翻转"><a href="#字符串翻转" class="headerlink" title="字符串翻转"></a>字符串翻转</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">strrev</span>(<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> ($str == <span class="string">''</span>) <span class="keyword">return</span> <span class="number">0</span> ;  </span><br><span class="line">    <span class="keyword">for</span> ($i=(strlen($str)- <span class="number">1</span>); $i&gt;=<span class="number">0</span>; $i --)&#123;  </span><br><span class="line">            $rev_str .= $str[$i ];  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $rev_str;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="字符串比较"><a href="#字符串比较" class="headerlink" title="字符串比较"></a>字符串比较</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">strcmp</span>(<span class="params">$s1,  $s2</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (strlen($s1) &lt;  strlen($s2)) <span class="keyword">return</span> <span class="number">-1</span> ;  </span><br><span class="line">    <span class="keyword">if</span> (strlen($s1) &gt; strlen( $s2)) <span class="keyword">return</span> <span class="number">1</span>;  </span><br><span class="line">    <span class="keyword">for</span> ($i =<span class="number">0</span>; $i&lt;strlen($s1 ); $i++)&#123;  </span><br><span class="line">            <span class="keyword">if</span> ($s1[ $i] == $s2[$i])&#123;  </span><br><span class="line">                    <span class="keyword">continue</span>;  </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;  </span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">false</span>;  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span>  <span class="number">0</span>;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="查找字符串"><a href="#查找字符串" class="headerlink" title="查找字符串"></a>查找字符串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span>  <span class="title">strstr</span>(<span class="params">$str, $substr</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">$m = strlen($str);  </span><br><span class="line">$n = strlen($substr );  </span><br><span class="line"><span class="keyword">if</span> ($m &lt; $n) <span class="keyword">return</span> <span class="literal">false</span> ;  </span><br><span class="line"><span class="keyword">for</span> ($i=<span class="number">0</span>; $i &lt;=($m-$n+<span class="number">1</span>); $i ++)&#123;  </span><br><span class="line">        $sub = substr( $str, $i, $n);  </span><br><span class="line">        <span class="keyword">if</span> ( strcmp($sub, $substr) ==  <span class="number">0</span>)  <span class="keyword">return</span> $i;  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="keyword">return</span> <span class="literal">false</span> ;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="字符串替换"><a href="#字符串替换" class="headerlink" title="字符串替换"></a>字符串替换</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">str_replace</span>(<span class="params">$substr , $newsubstr, $str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">$m = strlen($str);  </span><br><span class="line">$n = strlen($substr );  </span><br><span class="line">$x = strlen($newsubstr );  </span><br><span class="line"><span class="keyword">if</span> (strchr($str, $substr ) == <span class="literal">false</span>) <span class="keyword">return</span> <span class="literal">false</span>;  </span><br><span class="line"><span class="keyword">for</span> ( $i=<span class="number">0</span>; $i&lt;=($m- $n+<span class="number">1</span>); $i++)&#123;  </span><br><span class="line">         $i = strchr($str,  $substr);  </span><br><span class="line">        $str = str_delete ($str, $i, $n);  </span><br><span class="line">        $str = str_insert($str,  $i, $newstr);  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="keyword">return</span> $str ;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="自实现字符串处理函数"><a href="#自实现字符串处理函数" class="headerlink" title="自实现字符串处理函数"></a>自实现字符串处理函数</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">str_insert</span>(<span class="params">$str, $i , $substr</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">for</span>($j=<span class="number">0</span> ; $j&lt;$i; $j ++)&#123;  </span><br><span class="line">            $startstr .= $str[$j ];  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">for</span> ($j=$i; $j &lt;strlen($str); $j ++)&#123;  </span><br><span class="line">            $laststr .= $str[$j ];  </span><br><span class="line">    &#125;  </span><br><span class="line">    $str = ($startstr . $substr  . $laststr);  </span><br><span class="line">    <span class="keyword">return</span> $str ;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="删除一段字符串"><a href="#删除一段字符串" class="headerlink" title="删除一段字符串"></a>删除一段字符串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">str_delete</span>(<span class="params">$str , $i, $j</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">for</span> ( $c=<span class="number">0</span>; $c&lt;$i;  $c++)&#123;  </span><br><span class="line">            $startstr .= $str [$c];  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">for</span> ($c=( $i+$j); $c&lt;strlen ($str); $c++)&#123;  </span><br><span class="line">            $laststr  .= $str[$c];  </span><br><span class="line">    &#125;  </span><br><span class="line">     $str = ($startstr . $laststr );  </span><br><span class="line">    <span class="keyword">return</span> $str;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="复制字符串"><a href="#复制字符串" class="headerlink" title="复制字符串"></a>复制字符串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">strcpy</span>(<span class="params">$s1, $s2 </span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (strlen($s1)==NULL || !isset( $s2)) <span class="keyword">return</span>;  </span><br><span class="line">    <span class="keyword">for</span> ($i=<span class="number">0</span> ; $i&lt;strlen($s1);  $i++)&#123;  </span><br><span class="line">            $s2[] = $s1 [$i];  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $s2;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="连接字符串"><a href="#连接字符串" class="headerlink" title="连接字符串"></a>连接字符串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">strcat</span>(<span class="params">$s1 , $s2</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (!isset($s1) || !isset( $s2)) <span class="keyword">return</span>;  </span><br><span class="line">    $newstr = $s1 ;  </span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span>; $i &lt;count($s); $i ++)&#123;  </span><br><span class="line">            $newstr .= $st[$i ];  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $newsstr;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="简单编码函数（与php-decode函数对应）"><a href="#简单编码函数（与php-decode函数对应）" class="headerlink" title="简单编码函数（与php_decode函数对应）"></a>简单编码函数（与php_decode函数对应）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">php_encode</span>(<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line"><span class="keyword">if</span> ( $str==<span class="string">''</span> &amp;&amp; strlen( $str)&gt;<span class="number">128</span>) <span class="keyword">return</span> <span class="literal">false</span>;  </span><br><span class="line"><span class="keyword">for</span>( $i=<span class="number">0</span>; $i&lt;strlen ($str); $i++)&#123;  </span><br><span class="line">         $c = ord($str[$i ]);  </span><br><span class="line">        <span class="keyword">if</span> ($c&gt;<span class="number">31</span> &amp;&amp; $c &lt;<span class="number">107</span>) $c += <span class="number">20</span> ;  </span><br><span class="line">        <span class="keyword">if</span> ($c&gt;<span class="number">106</span> &amp;&amp; $c &lt;<span class="number">127</span>) $c -= <span class="number">75</span> ;  </span><br><span class="line">        $word = chr($c );  </span><br><span class="line">        $s .= $word;  </span><br><span class="line">&#125;   </span><br><span class="line"><span class="keyword">return</span> $s;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="简单解码函数（与php-encode函数对应）"><a href="#简单解码函数（与php-encode函数对应）" class="headerlink" title="简单解码函数（与php_encode函数对应）"></a>简单解码函数（与php_encode函数对应）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">php_decode</span>(<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line"><span class="keyword">if</span> ( $str==<span class="string">''</span> &amp;&amp; strlen($str )&gt;<span class="number">128</span>) <span class="keyword">return</span> <span class="literal">false</span>;  </span><br><span class="line"><span class="keyword">for</span>( $i=<span class="number">0</span>; $i&lt;strlen ($str); $i++)&#123;  </span><br><span class="line">        $c  = ord($word);  </span><br><span class="line">        <span class="keyword">if</span> ( $c&gt;<span class="number">106</span> &amp;&amp; $c&lt;<span class="number">127</span> ) $c = $c<span class="number">-20</span>;  </span><br><span class="line">        <span class="keyword">if</span> ($c&gt;<span class="number">31</span> &amp;&amp; $c&lt; <span class="number">107</span>) $c = $c+<span class="number">75</span> ;  </span><br><span class="line">        $word = chr( $c);  </span><br><span class="line">        $s .= $word ;  </span><br><span class="line">&#125;   </span><br><span class="line"><span class="keyword">return</span> $s;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="简单加密函数（与php-decrypt函数对应）"><a href="#简单加密函数（与php-decrypt函数对应）" class="headerlink" title="简单加密函数（与php_decrypt函数对应）"></a>简单加密函数（与php_decrypt函数对应）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">php_encrypt</span>(<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">     $encrypt_key = <span class="string">'abcdefghijklmnopqrstuvwxyz1234567890'</span>;  </span><br><span class="line">     $decrypt_key = <span class="string">'ngzqtcobmuhelkpdawxfyivrsj2468021359'</span>;  </span><br><span class="line">    <span class="keyword">if</span> ( strlen($str) == <span class="number">0</span>) <span class="keyword">return</span>  <span class="literal">false</span>;  </span><br><span class="line">    <span class="keyword">for</span> ($i=<span class="number">0</span>;  $i&lt;strlen($str); $i ++)&#123;  </span><br><span class="line">            <span class="keyword">for</span> ($j=<span class="number">0</span>; $j &lt;strlen($encrypt_key); $j ++)&#123;  </span><br><span class="line">                    <span class="keyword">if</span> ($str[$i] == $encrypt_key [$j])&#123;  </span><br><span class="line">                            $enstr .=  $decrypt_key[$j];  </span><br><span class="line">                            <span class="keyword">break</span>;  </span><br><span class="line">                    &#125;  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $enstr;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="简单解密函数（与php-encrypt函数对应）"><a href="#简单解密函数（与php-encrypt函数对应）" class="headerlink" title="简单解密函数（与php_encrypt函数对应）"></a>简单解密函数（与php_encrypt函数对应）</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">php_decrypt</span>(<span class="params">$str</span>)  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">     $encrypt_key = <span class="string">'abcdefghijklmnopqrstuvwxyz1234567890'</span>;  </span><br><span class="line">     $decrypt_key = <span class="string">'ngzqtcobmuhelkpdawxfyivrsj2468021359'</span>;  </span><br><span class="line">    <span class="keyword">if</span> ( strlen($str) == <span class="number">0</span>) <span class="keyword">return</span>  <span class="literal">false</span>;  </span><br><span class="line">    <span class="keyword">for</span> ($i=<span class="number">0</span>;  $i&lt;strlen($str); $i ++)&#123;  </span><br><span class="line">            <span class="keyword">for</span> ($j=<span class="number">0</span>; $j &lt;strlen($decrypt_key); $j ++)&#123;  </span><br><span class="line">                    <span class="keyword">if</span> ($str[$i] == $decrypt_key [$j])&#123;  </span><br><span class="line">                            $enstr .=  $encrypt_key[$j];  </span><br><span class="line">                            <span class="keyword">break</span>;  </span><br><span class="line">                    &#125;  </span><br><span class="line">            &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> $enstr;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="王者编程大赛之四-—-约瑟夫环"><a href="#王者编程大赛之四-—-约瑟夫环" class="headerlink" title="王者编程大赛之四 — 约瑟夫环"></a>王者编程大赛之四 — 约瑟夫环</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">约瑟夫环递推实现：https:<span class="comment">//www.fanhaobai.com/2017/12/2017-ziroom-king-4.html</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">josephus</span>(<span class="params">$n, $e</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $idx = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> ($i = <span class="number">2</span>; $i &lt;= $n; $i ++) &#123;</span><br><span class="line">        $idx = ($idx + $e) % $i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $idx;</span><br><span class="line">&#125;</span><br><span class="line">接收标准输入处理并输出结果：</span><br><span class="line"></span><br><span class="line">$input = str_replace(<span class="string">' '</span>, <span class="string">'&amp;'</span>, $input);</span><br><span class="line">parse_str($input, $arr);</span><br><span class="line">echo josephus($arr[<span class="string">'n'</span>], $arr[<span class="string">'e'</span>]), PHP_EOL;</span><br></pre></td></tr></table></figure>
<h3 id="阶梯式电费算法"><a href="#阶梯式电费算法" class="headerlink" title="阶梯式电费算法"></a>阶梯式电费算法</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line">举个栗子，深圳为了推进市民节约用电推出了这样一个用电收费政策，电量使用阶梯式递增的收费计算方式，简单而言、用电越多平均的每度电越贵。(假设用户的每电量为整数，小于<span class="number">1</span>度电则应缴费为<span class="number">0</span>元)</span><br><span class="line">  耗电范围(°) 	电费计算(<span class="number">1</span>元/°)</span><br><span class="line">  <span class="number">1</span>&lt;=x&lt;=<span class="number">10</span>   	        <span class="number">1</span>       </span><br><span class="line">  <span class="number">11</span>&lt;=x&lt;=<span class="number">20</span> 	       <span class="number">1.2</span>       </span><br><span class="line">  <span class="number">21</span>&lt;=x&lt;=<span class="number">50</span> 	       <span class="number">1.4</span>       </span><br><span class="line"><span class="number">51</span>&lt;=x&lt;=<span class="number">100</span> 	       <span class="number">1.8</span>       </span><br><span class="line"><span class="number">101</span>&lt;=x&lt;=<span class="number">300</span>	       <span class="number">2.4</span>       </span><br><span class="line">   <span class="number">301</span>&lt;=x   	        <span class="number">5</span>       </span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 根据用电的度数计算电费</span></span><br><span class="line"><span class="comment"> * @param int $number 用电度数</span></span><br><span class="line"><span class="comment"> * @return float 电费https://learnku.com/articles/24977</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">calculate</span>(<span class="params">int $number</span>): <span class="title">float</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($number &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">switch</span> ($number) &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">1</span> &lt;= $number &amp;&amp; $number &lt;= <span class="number">10</span>:</span><br><span class="line">            <span class="keyword">return</span> $number * <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">11</span> &lt;= $number &amp;&amp; $number &lt;= <span class="number">20</span>:</span><br><span class="line">            <span class="keyword">return</span> ($number - <span class="number">10</span>) * <span class="number">1.2</span> + calculate(<span class="number">10</span>);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">21</span> &lt;= $number &amp;&amp; $number &lt;= <span class="number">50</span>:</span><br><span class="line">            <span class="keyword">return</span> ($number - <span class="number">20</span>) * <span class="number">1.4</span> + calculate(<span class="number">20</span>);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">51</span> &lt;= $number &amp;&amp; $number &lt;= <span class="number">100</span>:</span><br><span class="line">            <span class="keyword">return</span> ($number - <span class="number">50</span>) * <span class="number">1.8</span> + calculate(<span class="number">50</span>);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">101</span> &lt;= $number &amp;&amp; $number &lt;= <span class="number">300</span>:</span><br><span class="line">            <span class="keyword">return</span> ($number - <span class="number">100</span>) * <span class="number">2.2</span> + calculate(<span class="number">100</span>);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="keyword">return</span> ($number - <span class="number">300</span>) * <span class="number">5</span> + calculate(<span class="number">300</span>);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">calculate</span>(<span class="params">int $useNum</span>): <span class="title">float</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($useNum &lt; <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 电费价格及其范围的配置定义 | 此梯度可抽出来独立配置</span></span><br><span class="line">    $degrees = [<span class="number">10</span>, <span class="number">20</span>, <span class="number">50</span>, <span class="number">100</span>, <span class="number">300</span>];</span><br><span class="line">    $prices  = [<span class="number">1</span>, <span class="number">1.2</span>, <span class="number">1.4</span>, <span class="number">1.8</span>, <span class="number">2.4</span>, <span class="number">5</span>];</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 判断是否达到最贵的价格梯度并计算其价格</span></span><br><span class="line">    $beyondNum = $useNum - end($degrees);</span><br><span class="line">    $price     = ($beyondNum &gt;= <span class="number">0</span> ? $beyondNum : <span class="number">0</span>) * end($prices);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 上一层价格峰值</span></span><br><span class="line">    $prePeak = <span class="number">0</span>;</span><br><span class="line">    foreach ($degrees <span class="keyword">as</span> $key =&gt; $value) &#123;</span><br><span class="line">        <span class="keyword">if</span> ($useNum &lt;= $value) &#123;</span><br><span class="line">            $price += ($useNum - $prePeak) * $prices[$key];</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        $price   += ($value - $prePeak) * $prices[$key];</span><br><span class="line">        $prePeak = $value;</span><br><span class="line">    &#125;</span><br><span class="line">    unset($degrees, $prices, $beyondNum, $prePeak);</span><br><span class="line">    <span class="keyword">return</span> $price;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="按照奖品概率分布抽奖"><a href="#按照奖品概率分布抽奖" class="headerlink" title="按照奖品概率分布抽奖"></a>按照奖品概率分布抽奖</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//所有奖品信息</span></span><br><span class="line">$allPrizes = [</span><br><span class="line">  <span class="string">'jd'</span>    =&gt; [<span class="string">'name'</span> =&gt; <span class="string">'京东券'</span>, <span class="string">'probability'</span> =&gt; <span class="number">30</span>],</span><br><span class="line">  <span class="string">'film'</span>  =&gt; [<span class="string">'name'</span> =&gt; <span class="string">'电影票'</span>, <span class="string">'probability'</span> =&gt; <span class="number">10</span>],</span><br><span class="line">  <span class="string">'tb'</span>    =&gt; [<span class="string">'name'</span> =&gt; <span class="string">'淘宝券'</span>, <span class="string">'probability'</span> =&gt; <span class="number">60</span>],</span><br><span class="line">]</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 按照概率抽取一个奖品, 返回奖品</span></span><br><span class="line"><span class="comment"> * @param   array      $prizes     所有奖品的probability概率总和应该为100</span></span><br><span class="line"><span class="comment"> * @return  mixed</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">randPrize</span>(<span class="params">array $prizes</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//总概率基数</span></span><br><span class="line">    $totalProbability = array_sum(array_column(array_values($prizes), <span class="string">'probability'</span>));</span><br><span class="line">    <span class="keyword">if</span> (<span class="number">100</span> !== $totalProbability) &#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> Exception(<span class="string">'invalid probability config'</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    $rand = mt_rand(<span class="number">1</span>, <span class="number">100</span>);</span><br><span class="line">    $cursor = <span class="number">0</span>;</span><br><span class="line">    $id = <span class="string">''</span>;</span><br><span class="line">    <span class="keyword">while</span>(list($key, $item) = each($prizes)) &#123;</span><br><span class="line">        <span class="keyword">if</span> ($rand &gt; $cursor &amp;&amp; $rand &lt;= $cursor + $item[<span class="string">'probability'</span>]) &#123;</span><br><span class="line">            $id = $key;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        $cursor += $item[<span class="string">'probability'</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    unset($prizes[$id][<span class="string">'probability'</span>]);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> $prizes[$id] + [<span class="string">'id'</span> =&gt; $id];</span><br><span class="line">&#125;</span><br><span class="line">https:<span class="comment">//www.fanhaobai.com/2017/05/draw-by-prob.html</span></span><br></pre></td></tr></table></figure>
<h3 id="非负元素数组所有元素能组合的最大字符串"><a href="#非负元素数组所有元素能组合的最大字符串" class="headerlink" title="非负元素数组所有元素能组合的最大字符串"></a>非负元素数组所有元素能组合的最大字符串</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line">[<span class="number">0</span>, <span class="number">9</span>, <span class="number">523</span>, <span class="number">94</span>, <span class="number">10</span>, <span class="number">4</span>]，排列组合后值最大数为：<span class="number">9945234100</span>。</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 比较规则</span></span><br><span class="line"><span class="comment"> * @param   string    $a</span></span><br><span class="line"><span class="comment"> * @param   string    $b</span></span><br><span class="line"><span class="comment"> * @return  int</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">cmp</span>(<span class="params">$a, $b</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($a == $b) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $a . $b &gt; $b . $a ? <span class="number">-1</span> : <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 冒泡排序</span></span><br><span class="line"><span class="comment"> * @param   array    $Arr   待排序数组</span></span><br><span class="line"><span class="comment"> * @return  array</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bubble_sort</span>(<span class="params">array $Arr</span>) </span>&#123;</span><br><span class="line">    $length = count($Arr);</span><br><span class="line">	<span class="keyword">if</span> ($length &lt; <span class="number">2</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> $Arr;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> ($i = <span class="number">1</span>, $change = <span class="literal">true</span>; $i &lt;= $length &amp;&amp; $change; $i++) &#123;</span><br><span class="line">        $change = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">for</span> ($j = $length - <span class="number">1</span>; $j &gt; $i - <span class="number">1</span>; $j--) &#123;</span><br><span class="line">            <span class="keyword">if</span> (cmp($Arr[$j - <span class="number">1</span>], $Arr[$j]) &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                $temp = $Arr[$j - <span class="number">1</span>];</span><br><span class="line">                $Arr[$j - <span class="number">1</span>] = $Arr[$j];</span><br><span class="line">                $Arr[$j] = $temp;</span><br><span class="line">                $change = <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $Arr;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 寻找非零元素数组中所有元素排列组合后的最大值</span></span><br><span class="line"><span class="comment"> * @param   array     $Arr        待排序数组</span></span><br><span class="line"><span class="comment"> * @param   string    $method     排序方法</span></span><br><span class="line"><span class="comment"> * @return  mixed</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">array_form_max_str</span>(<span class="params">array $Arr, $method = <span class="string">'bubble'</span></span>) </span>&#123;</span><br><span class="line">    <span class="comment">//参数校验</span></span><br><span class="line">    <span class="keyword">if</span> (!is_array($Arr)) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    foreach ($Arr <span class="keyword">as</span> $value) &#123;</span><br><span class="line">        <span class="keyword">if</span> ($value &lt; <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//排序算法</span></span><br><span class="line">    <span class="keyword">switch</span> ($method) &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">'quick'</span> :</span><br><span class="line">            usort($Arr, <span class="string">"cmp"</span>);           <span class="comment">//快速排序</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">'bubble'</span> :</span><br><span class="line">            $Arr = bubble_sort($Arr);     <span class="comment">//冒泡排序</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">default</span> : <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//拼接</span></span><br><span class="line">    <span class="keyword">return</span> implode(<span class="string">''</span>, $Arr);</span><br><span class="line">&#125;</span><br><span class="line">$Arr = [<span class="number">20</span>,<span class="number">913</span>,<span class="number">223</span>,<span class="number">91</span>,<span class="number">20</span>,<span class="number">3</span>];</span><br><span class="line">echo <span class="string">'数组为['</span>, implode(<span class="string">','</span>, $Arr), <span class="string">']'</span>, PHP_EOL;</span><br><span class="line">echo <span class="string">'最大排列组合为：'</span>, array_form_max_str($Arr), PHP_EOL;</span><br><span class="line"></span><br><span class="line">https:<span class="comment">//www.fanhaobai.com/2017/04/array-form-max-string.html</span></span><br></pre></td></tr></table></figure>
<h3 id="PHP生成随机红包算法"><a href="#PHP生成随机红包算法" class="headerlink" title="PHP生成随机红包算法"></a>PHP生成随机红包算法</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br></pre></td><td class="code"><pre><span class="line">原文：比如要把 <span class="number">1</span> 个红包分给 N 个人，实际上就是相当于要得到 N 个百分比数据 条件是这 N 个百分比之和 = <span class="number">100</span>/<span class="number">100</span>。这 N 个百分比的平均值是 <span class="number">1</span>/N。 并且这 N 个百分比数据符合一种正态分布（多数值比较靠近平均值）。</span><br><span class="line">解读：比如我有 <span class="number">1000</span> 块钱，发 <span class="number">50</span> 个红包，就先随机出 <span class="number">50</span> 个数，然后算出这 <span class="number">50</span> 个数的均值 avg，用 avg/(<span class="number">1</span>/N)，就得到了一个基数 mixrand ，然后用随机出的那 <span class="number">50</span> 个数分别去除以 mixrand ，得到每个数相对基数的百分比 randVal ，然后用 randVal 乘以 <span class="number">1000</span> 块钱，就可以得到每个红包的具体金额了。</span><br><span class="line">https:<span class="comment">//www.fanhaobai.com/2017/02/reward.html</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Reward</span></span></span><br><span class="line"><span class="class"></span>&#123;</span><br><span class="line">    public $rewardMoney;        #红包金额、单位元</span><br><span class="line">    public $rewardNum;          #红包数量</span><br><span class="line"></span><br><span class="line">    #执行红包生成算法</span><br><span class="line">    public <span class="function"><span class="keyword">function</span> <span class="title">splitReward</span>(<span class="params">$rewardMoney, $rewardNum, $max, $min</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        #传入红包金额和数量，因为小数在计算过程中会出现很大误差，所以我们直接把金额放大100倍，后面的计算全部用整数进行</span><br><span class="line">        $min = $min * <span class="number">100</span>;</span><br><span class="line">        $max = $max * <span class="number">100</span>;</span><br><span class="line">        #预留出一部分钱作为误差补偿，保证每个红包至少有一个最小值</span><br><span class="line">        $<span class="keyword">this</span>-&gt;rewardMoney = $rewardMoney * <span class="number">100</span> - $rewardNum * $min;</span><br><span class="line">        $<span class="keyword">this</span>-&gt;rewardNum = $rewardNum;</span><br><span class="line">        #计算出发出红包的平均概率值、精确到小数4位。</span><br><span class="line">        $avgRand = <span class="number">1</span> / $<span class="keyword">this</span>-&gt;rewardNum;</span><br><span class="line">        $randArr = array();</span><br><span class="line">        #定义生成的数据总合sum</span><br><span class="line">        $sum = <span class="number">0</span>;</span><br><span class="line">        $t_count = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> ($t_count &lt; $rewardNum) &#123;</span><br><span class="line">            #随机产出四个区间的额度</span><br><span class="line">            $c = rand(<span class="number">1</span>, <span class="number">100</span>);</span><br><span class="line">            <span class="keyword">if</span> ($c &lt; <span class="number">15</span>) &#123;</span><br><span class="line">                $t = round(sqrt(mt_rand(<span class="number">1</span>, <span class="number">1500</span>)));</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> ($c &lt; <span class="number">65</span>) &#123;</span><br><span class="line">                $t = round(sqrt(mt_rand(<span class="number">1500</span>, <span class="number">6500</span>)));</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> ($c &lt; <span class="number">95</span>) &#123;</span><br><span class="line">                $t = round(sqrt(mt_rand(<span class="number">6500</span>, <span class="number">9500</span>)));</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                $t = round(sqrt(mt_rand(<span class="number">9500</span>, <span class="number">10000</span>)));</span><br><span class="line">            &#125;</span><br><span class="line">            ++$t_count;</span><br><span class="line">            $sum += $t;</span><br><span class="line">            $randArr[] = $t;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        #计算当前生成的随机数的平均值，保留4位小数</span><br><span class="line">        $randAll = round($sum / $rewardNum, <span class="number">4</span>);</span><br><span class="line"></span><br><span class="line">        #为将生成的随机数的平均值变成我们要的1/N，计算一下每个随机数要除以的总基数mixrand。此处可以约等处理，产生的误差后边会找齐</span><br><span class="line">        #总基数 = 均值/平均概率</span><br><span class="line">        $mixrand = round($randAll / $avgRand, <span class="number">4</span>);</span><br><span class="line"></span><br><span class="line">        #对每一个随机数进行处理，并乘以总金额数来得出这个红包的金额。</span><br><span class="line">        $rewardArr = array();</span><br><span class="line">        foreach ($randArr <span class="keyword">as</span> $key =&gt; $randVal) &#123;</span><br><span class="line">            #单个红包所占比例randVal</span><br><span class="line">            $randVal = round($randVal / $mixrand, <span class="number">4</span>);</span><br><span class="line">            #算出单个红包金额</span><br><span class="line">            $single = floor($<span class="keyword">this</span>-&gt;rewardMoney * $randVal);</span><br><span class="line">            #小于最小值直接给最小值</span><br><span class="line">            <span class="keyword">if</span> ($single &lt; $min) &#123;</span><br><span class="line">                $single += $min;</span><br><span class="line">            &#125;</span><br><span class="line">            #大于最大值直接给最大值</span><br><span class="line">            <span class="keyword">if</span> ($single &gt; $max) &#123;</span><br><span class="line">                $single = $max;</span><br><span class="line">            &#125;</span><br><span class="line">            #将红包放入结果数组</span><br><span class="line">            $rewardArr[] = $single;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        #对比红包总数的差异、将差值放在第一个红包上</span><br><span class="line">        $rewardAll = array_sum($rewardArr);</span><br><span class="line">        #此处应使用真正的总金额rewardMoney，$rewardArr[0]可能小于0</span><br><span class="line">        $rewardArr[<span class="number">0</span>] = $rewardMoney * <span class="number">100</span> - ($rewardAll - $rewardArr[<span class="number">0</span>]);</span><br><span class="line">        #第一个红包小于0时,做修正</span><br><span class="line">        <span class="keyword">if</span> ($rewardArr[<span class="number">0</span>] &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            rsort($rewardArr);</span><br><span class="line">            $<span class="keyword">this</span>-&gt;add($rewardArr, $min);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        rsort($rewardArr);</span><br><span class="line">        #随机生成的最大值大于指定最大值</span><br><span class="line">        <span class="keyword">if</span> ($rewardArr[<span class="number">0</span>] &gt; $max) &#123;</span><br><span class="line">            #差额</span><br><span class="line">            $diff = <span class="number">0</span>;</span><br><span class="line">            foreach ($rewardArr <span class="keyword">as</span> $k =&gt; &amp;$v) &#123;</span><br><span class="line">                <span class="keyword">if</span> ($v &gt; $max) &#123;</span><br><span class="line">                    $diff += $v - $max;</span><br><span class="line">                    $v = $max;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            $transfer = round($diff / ($<span class="keyword">this</span>-&gt;rewardNum - $k + <span class="number">1</span>));</span><br><span class="line">            $<span class="keyword">this</span>-&gt;diff($diff, $rewardArr, $max, $min, $transfer, $k);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> $rewardArr;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    #处理所有超过最大值的红包</span><br><span class="line">    public <span class="function"><span class="keyword">function</span> <span class="title">diff</span>(<span class="params">$diff, &amp;$rewardArr, $max, $min, $transfer, $k</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        #将多余的钱均摊给小于最大值的红包</span><br><span class="line">        <span class="keyword">for</span> ($i = $k; $i &lt; $<span class="keyword">this</span>-&gt;rewardNum; $i++) &#123;</span><br><span class="line">            #造随机值</span><br><span class="line">            <span class="keyword">if</span> ($transfer &gt; $min * <span class="number">20</span>) &#123;</span><br><span class="line">                $aa = rand($min, $min * <span class="number">20</span>);</span><br><span class="line">                <span class="keyword">if</span> ($i % <span class="number">2</span>) &#123;</span><br><span class="line">                    $transfer += $aa;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    $transfer -= $aa;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> ($rewardArr[$i] + $transfer &gt; $max) <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">if</span> ($diff - $transfer &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                $rewardArr[$i] += $diff;</span><br><span class="line">                $diff = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            $rewardArr[$i] += $transfer;</span><br><span class="line">            $diff -= $transfer;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ($diff &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            $i++;</span><br><span class="line">            $<span class="keyword">this</span>-&gt;diff($diff, $rewardArr, $max, $min, $transfer, $k);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    #第一个红包小于0,从大红包上往下减</span><br><span class="line">    public <span class="function"><span class="keyword">function</span> <span class="title">add</span>(<span class="params">&amp;$rewardArr, $min</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        foreach ($rewardArr <span class="keyword">as</span> &amp;$re) &#123;</span><br><span class="line">            $dev = floor($re / $min);</span><br><span class="line">            <span class="keyword">if</span> ($dev &gt; <span class="number">2</span>) &#123;</span><br><span class="line">                $transfer = $min * floor($dev / <span class="number">2</span>);</span><br><span class="line">                $re -= $transfer;</span><br><span class="line">                $rewardArr[$<span class="keyword">this</span>-&gt;rewardNum - <span class="number">1</span>] += $transfer;</span><br><span class="line">            &#125; elseif ($dev == <span class="number">2</span>) &#123;</span><br><span class="line">                $re -= $min;</span><br><span class="line">                $rewardArr[$<span class="keyword">this</span>-&gt;rewardNum - <span class="number">1</span>] += $min;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ($rewardArr[$<span class="keyword">this</span>-&gt;rewardNum - <span class="number">1</span>] &gt; $min || $rewardArr[$<span class="keyword">this</span>-&gt;rewardNum - <span class="number">1</span>] == $min) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            $<span class="keyword">this</span>-&gt;add($rewardArr, $min);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//https://github.com/xxlufei/reward</span></span><br></pre></td></tr></table></figure>
<h3 id="复杂度"><a href="#复杂度" class="headerlink" title="复杂度"></a>复杂度</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">sum = n*(n+<span class="number">1</span>)/<span class="number">2</span>;        <span class="comment">//时间复杂度O(1)</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(int i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">    printf(<span class="string">"%d "</span>,i);</span><br><span class="line">&#125;                       </span><br><span class="line"><span class="comment">//时间复杂度O(n)</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(int i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">    <span class="keyword">for</span>(int j = <span class="number">0</span>; j &lt; n; j++)&#123;</span><br><span class="line">        printf(<span class="string">"%d "</span>,i);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;               </span><br><span class="line"><span class="comment">//时间复杂度O(n^2)</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(int i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">    <span class="keyword">for</span>(int j = i; j &lt; n; j++)&#123;</span><br><span class="line">        printf(<span class="string">"%d "</span>,i);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;   </span><br><span class="line"><span class="comment">//运行次数为(1+n)*n/2</span></span><br><span class="line"><span class="comment">//时间复杂度O(n^2)</span></span><br><span class="line">int i = <span class="number">0</span>, n = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">while</span>(i &lt; n)&#123;</span><br><span class="line">    i = i * <span class="number">2</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//设执行次数为x. 2^x = n 即x = log2n</span></span><br><span class="line"><span class="comment">//时间复杂度O(log2n)</span></span><br><span class="line">常用排序算法的时间复杂度https:<span class="comment">//learnku.com/articles/25297</span></span><br><span class="line"></span><br><span class="line">算法	最差时间分析	平均时间复杂度	稳定度	空间复杂度</span><br><span class="line">冒泡排序	O(n2)	O(n2)	稳定	O(<span class="number">1</span>)</span><br><span class="line">快速排序	O(n2)	O(n*log2n)	不稳定	O(log2n)~O(n)</span><br><span class="line">选择排序	O(n2)	O(n2)	稳定	O(<span class="number">1</span>)</span><br><span class="line">二叉树排序	O(n2)	O(n*log2n)	不稳定	O(n)</span><br><span class="line">插入排序	O(n2)	O(n2)	稳定	O(<span class="number">1</span>)</span><br><span class="line">堆排序	O(n*log2n)	O(n*log2n)	不稳定	O(<span class="number">1</span>)</span><br><span class="line">希尔排序	O	O	不稳定	O(<span class="number">1</span>)</span><br></pre></td></tr></table></figure>
<h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">public <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">quick</span>(<span class="params">$arr</span>)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(count($arr)&lt;=<span class="number">1</span>)&#123; <span class="comment">//如果数组根本就一个元素就直接返回 不用在排序咯https://learnku.com/articles/25865</span></span><br><span class="line">            <span class="keyword">return</span> $arr;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        $k=$arr[<span class="number">0</span>];<span class="comment">//定义一个初始要排序的值 默认为数组第一个</span></span><br><span class="line">        $x=array();<span class="comment">//定义比要排序的值 小的数组块</span></span><br><span class="line">        $y=array();<span class="comment">//定义比要排序的值 大的数组块</span></span><br><span class="line">        $_size=count($arr);<span class="comment">//统计数组的大小</span></span><br><span class="line">        <span class="keyword">for</span>($i=<span class="number">1</span>;$i&lt;$_size;$i++)&#123;<span class="comment">//循环数组 记住这边要从索引1 开始</span></span><br><span class="line">            <span class="keyword">if</span>($arr[$i]&lt;=$k)&#123;<span class="comment">//如果当前的值小于 要排序的值</span></span><br><span class="line">                $x[]=$arr[$i];<span class="comment">//就把小于的值放到 小的数组块中</span></span><br><span class="line">            &#125;elseif($arr[$i]&gt;$k)&#123;<span class="comment">//如果当前的值大于 要排序的值</span></span><br><span class="line">                $y[]=$arr[$i];<span class="comment">//就把大于的值放到 大的数组块中</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        $x=Sort::quick($x);<span class="comment">//依次递归执行 这样就会得到小的数组块</span></span><br><span class="line">        $y=Sort::quick($y);<span class="comment">//依次递归执行 这样就会得到大的数组块</span></span><br><span class="line">        <span class="keyword">return</span> array_merge($x,array($k),$y);<span class="comment">//最后在合并下 小的模块+中间的模块【初始要排序的值】+大的模块 就ok~</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// print_r(Sort::quick($arr));</span></span><br></pre></td></tr></table></figure>
<h3 id="雪花算法"><a href="#雪花算法" class="headerlink" title="雪花算法"></a>雪花算法</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br></pre></td><td class="code"><pre><span class="line">最高位是符号位，始终为<span class="number">0</span>，不可用</span><br><span class="line">接下来的<span class="number">41</span>位为毫秒级时间(<span class="number">41</span>位的长度可以使用<span class="number">69</span>年)</span><br><span class="line">然后是<span class="number">5</span>位datacenterId和<span class="number">5</span>位workerId(<span class="number">10</span>位的长度最多支持部署<span class="number">1024</span>个节点）</span><br><span class="line">最后<span class="number">12</span>位是毫秒内的计数（<span class="number">12</span>位的计数顺序号支持每个节点每毫秒产生<span class="number">4096</span>个ID序号）</span><br><span class="line">一共加起来刚好<span class="number">64</span>位，为一个Long型。(转换成字符串后长度最多<span class="number">19</span>)</span><br><span class="line"></span><br><span class="line">snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生<span class="number">26</span>万个ID。</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SnowFlake</span></span>&#123;</span><br><span class="line">    public <span class="function"><span class="keyword">function</span> <span class="title">createID</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">        <span class="comment">//假设一个机器idhttps://ctexthuang.com/archives/6/</span></span><br><span class="line">        $machineId = <span class="number">1234567890</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//41bit timestamp(毫秒)</span></span><br><span class="line">        $time = floor(microtime(<span class="literal">true</span>) * <span class="number">1000</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//0bit 未使用</span></span><br><span class="line">        $suffix = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//datacenterId  添加数据的时间</span></span><br><span class="line">        $base = decbin(pow(<span class="number">2</span>,<span class="number">40</span>) - <span class="number">1</span> + $time);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//workerId  机器ID</span></span><br><span class="line">        $machineid = decbin(pow(<span class="number">2</span>,<span class="number">9</span>) - <span class="number">1</span> + $machineId);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//毫秒类的计数</span></span><br><span class="line">        $random = mt_rand(<span class="number">1</span>, pow(<span class="number">2</span>,<span class="number">11</span>)<span class="number">-1</span>);</span><br><span class="line"></span><br><span class="line">        $random = decbin(pow(<span class="number">2</span>,<span class="number">11</span>)<span class="number">-1</span> + $random);         </span><br><span class="line">        <span class="comment">//拼装所有数据</span></span><br><span class="line">        $base64 = $suffix.$base.$machineid.$random;</span><br><span class="line">        <span class="comment">//将二进制转换int</span></span><br><span class="line">        $base64 = bindec($base64);</span><br><span class="line"></span><br><span class="line">        $id = sprintf(<span class="string">'%.0f'</span>, $base64);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> $id;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">namespace EasySwoole\Core\Utility;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 雪花算法生成器</span></span><br><span class="line"><span class="comment"> * Class SnowFlake</span></span><br><span class="line"><span class="comment"> * @author : evalor &lt;master@evalor.cn&gt;</span></span><br><span class="line"><span class="comment"> * @package EasySwoole\Core\Utility</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SnowFlake</span></span></span><br><span class="line"><span class="class"></span>&#123;</span><br><span class="line">    private <span class="keyword">static</span> $lastTimestamp = <span class="number">0</span>;</span><br><span class="line">    private <span class="keyword">static</span> $lastSequence  = <span class="number">0</span>;</span><br><span class="line">    private <span class="keyword">static</span> $sequenceMask  = <span class="number">4095</span>;</span><br><span class="line">    private <span class="keyword">static</span> $twepoch       = <span class="number">1508945092000</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 生成基于雪花算法的随机编号</span></span><br><span class="line"><span class="comment">     * @author : evalor &lt;master@evalor.cn&gt;</span></span><br><span class="line"><span class="comment">     * @param int $dataCenterID 数据中心ID 0-31</span></span><br><span class="line"><span class="comment">     * @param int $workerID 任务进程ID 0-31</span></span><br><span class="line"><span class="comment">     * @return int 分布式ID</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">make</span>(<span class="params">$dataCenterID = <span class="number">0</span>, $workerID = <span class="number">0</span></span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="comment">// 41bit timestamp + 5bit dataCenter + 5bit worker + 12bit</span></span><br><span class="line"></span><br><span class="line">        $timestamp = self::timeGen();</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (self::$lastTimestamp == $timestamp) &#123;</span><br><span class="line">            self::$lastSequence = (self::$lastSequence + <span class="number">1</span>) &amp; self::$sequenceMask;</span><br><span class="line">            <span class="keyword">if</span> (self::$lastSequence == <span class="number">0</span>) $timestamp = self::tilNextMillis(self::$lastTimestamp);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            self::$lastSequence = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        self::$lastTimestamp = $timestamp;</span><br><span class="line"></span><br><span class="line">        $snowFlakeId = (($timestamp - self::$twepoch) &lt;&lt; <span class="number">22</span>) | ($dataCenterID &lt;&lt; <span class="number">17</span>) | ($workerID &lt;&lt; <span class="number">12</span>) | self::$lastSequence;</span><br><span class="line">        <span class="keyword">return</span> $snowFlakeId;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 反向解析雪花算法生成的编号</span></span><br><span class="line"><span class="comment">     * @author : evalor &lt;master@evalor.cn&gt;</span></span><br><span class="line"><span class="comment">     * @param int|float $snowFlakeId</span></span><br><span class="line"><span class="comment">     * @return \stdClass</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">unmake</span>(<span class="params">$snowFlakeId</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        $Binary               = str_pad(decbin($snowFlakeId), <span class="number">64</span>, <span class="string">'0'</span>, STR_PAD_LEFT);</span><br><span class="line">        $<span class="built_in">Object</span>               = <span class="keyword">new</span> \stdClass;</span><br><span class="line">        $<span class="built_in">Object</span>-&gt;timestamp    = bindec(substr($Binary, <span class="number">0</span>, <span class="number">41</span>)) + self::$twepoch;</span><br><span class="line">        $<span class="built_in">Object</span>-&gt;dataCenterID = bindec(substr($Binary, <span class="number">42</span>, <span class="number">5</span>));</span><br><span class="line">        $<span class="built_in">Object</span>-&gt;workerID     = bindec(substr($Binary, <span class="number">47</span>, <span class="number">5</span>));</span><br><span class="line">        $<span class="built_in">Object</span>-&gt;sequence     = bindec(substr($Binary, <span class="number">-12</span>));</span><br><span class="line">        <span class="keyword">return</span> $<span class="built_in">Object</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 等待下一毫秒的时间戳</span></span><br><span class="line"><span class="comment">     * @author : evalor &lt;master@evalor.cn&gt;</span></span><br><span class="line"><span class="comment">     * @param $lastTimestamp</span></span><br><span class="line"><span class="comment">     * @return float</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    private <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">tilNextMillis</span>(<span class="params">$lastTimestamp</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        $timestamp = self::timeGen();</span><br><span class="line">        <span class="keyword">while</span> ($timestamp &lt;= $lastTimestamp) &#123;</span><br><span class="line">            $timestamp = self::timeGen();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> $timestamp;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 获取毫秒级时间戳https://www.libenfu.com/index.php/archives/302/</span></span><br><span class="line"><span class="comment">     * @author : evalor &lt;master@evalor.cn&gt;</span></span><br><span class="line"><span class="comment">     * @return float</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    private <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">timeGen</span>(<span class="params"></span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (float)sprintf(<span class="string">'%.0f'</span>, microtime(<span class="literal">true</span>) * <span class="number">1000</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="number">1</span>bit正负标识位 - <span class="number">41</span>bits毫秒级时间戳 - <span class="number">5</span>bits数据中心id - <span class="number">5</span>bits机器id <span class="number">-12</span>bits毫秒内顺序id</span><br><span class="line">composer <span class="built_in">require</span> wantp/snowflake</span><br><span class="line">https:<span class="comment">//github.com/wantp/snowflake</span></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 分布式 id 生成类     组成: &lt;毫秒级时间戳+机器id+序列号&gt;</span></span><br><span class="line"><span class="comment">     * 默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，</span></span><br><span class="line"><span class="comment">      *序列号支持1毫秒产生4095个自增序列id</span></span><br><span class="line"><span class="comment">     * @author zhangqi</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="class"><span class="keyword">class</span> <span class="title">IdCreate</span></span></span><br><span class="line"><span class="class">    </span>&#123;</span><br><span class="line">      <span class="keyword">const</span> EPOCH = <span class="number">1479533469598</span>; <span class="comment">//开始时间,固定一个小于当前时间的毫秒数\</span></span><br><span class="line">      <span class="keyword">const</span> max12bit = <span class="number">4095</span>;</span><br><span class="line">      <span class="keyword">const</span> max41bit = <span class="number">1099511627775</span>;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">static</span> $machineId = <span class="literal">null</span>; <span class="comment">// 机器id</span></span><br><span class="line"></span><br><span class="line">      public <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">machineId</span>(<span class="params">$mId = <span class="number">0</span></span>)</span></span><br><span class="line"><span class="function">      </span>&#123;</span><br><span class="line">             self::$machineId = $mId;</span><br><span class="line">      &#125;</span><br><span class="line">      public <span class="keyword">static</span> <span class="function"><span class="keyword">function</span> <span class="title">createOnlyId</span>(<span class="params"></span>)</span></span><br><span class="line"><span class="function">     </span>&#123;</span><br><span class="line">         <span class="comment">// 时间戳 42字节</span></span><br><span class="line">         $time = floor(microtime(<span class="literal">true</span>) * <span class="number">1000</span>);</span><br><span class="line">          <span class="comment">// 当前时间 与 开始时间 差值</span></span><br><span class="line">        $time -= self::EPOCH;</span><br><span class="line">        <span class="comment">// 二进制的 毫秒级时间戳</span></span><br><span class="line">        $base = decbin(self::max41bit + $time);</span><br><span class="line">        <span class="comment">// 机器id  10 字节</span></span><br><span class="line">           <span class="keyword">if</span> (!self::$machineId) &#123;</span><br><span class="line">                   $machineid = self::$machineId;</span><br><span class="line">             &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    $machineid = str_pad(decbin(self::$machineId), <span class="number">10</span>, <span class="string">"0"</span>, STR_PAD_LEFT);\</span><br><span class="line">              &#125;</span><br><span class="line">             <span class="comment">// 序列数 12字节</span></span><br><span class="line">              $random = str_pad(decbin(mt_rand(<span class="number">0</span>, <span class="attr">self</span>::max12bit)), <span class="number">12</span>, <span class="string">"0"</span>, STR_PAD_LEFT);\</span><br><span class="line">              <span class="comment">// 拼接</span></span><br><span class="line">              $base = $base . $machineid . $random;</span><br><span class="line">              <span class="comment">// 转化为 十进制 返回</span></span><br><span class="line">              <span class="keyword">return</span> bindec($base);</span><br><span class="line">             &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    调用  IdCreate::createOnlyId(<span class="number">1</span>);</span><br><span class="line">           返回的值   <span class="comment">// 2219944901359</span></span><br><span class="line">           返回的值 <span class="comment">// 2220004015923</span></span><br><span class="line">           返回的值 <span class="comment">// 2220062766757</span></span><br><span class="line">           返回的值     <span class="comment">// 2220119764908</span></span><br></pre></td></tr></table></figure>
<h3 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//https://learnku.com/laravel/t/28462</span></span><br><span class="line">执行次数 T (n) 是关于问题规模 n 的函数</span><br><span class="line">常数阶</span><br><span class="line"></span><br><span class="line">复杂度为 O (<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line">线性阶</span><br><span class="line"></span><br><span class="line">int i;</span><br><span class="line"><span class="keyword">for</span>(i = <span class="number">0</span> ; i &lt; n ; i++)&#123;</span><br><span class="line">    <span class="comment">//代码</span></span><br><span class="line">&#125;</span><br><span class="line">复杂度为 O (n)</span><br><span class="line"></span><br><span class="line">对数阶</span><br><span class="line"></span><br><span class="line">int count = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">while</span>(count &lt; n)&#123;</span><br><span class="line">  count = count * <span class="number">2</span>;</span><br><span class="line">  <span class="comment">//代码  </span></span><br><span class="line">&#125;</span><br><span class="line">数学公式：<span class="number">2</span>x = n --&gt; x = log2n</span><br><span class="line"></span><br><span class="line">因此这个循环的时间复杂度为 O (logn)</span><br><span class="line"></span><br><span class="line">平方阶</span><br><span class="line"></span><br><span class="line">类型 <span class="number">1</span>：n*n</span><br><span class="line"></span><br><span class="line">int i;</span><br><span class="line"><span class="keyword">for</span>(i = <span class="number">0</span> ; i &lt; n ; i++)&#123;</span><br><span class="line">   <span class="keyword">for</span>(j = <span class="number">0</span> ; j &lt; n ; j++)&#123;</span><br><span class="line">    <span class="comment">//代码   </span></span><br><span class="line">   &#125;    </span><br><span class="line">&#125;</span><br><span class="line">时间复杂度为 O (n^<span class="number">2</span>^)。</span><br><span class="line"></span><br><span class="line">类型 <span class="number">2</span>：n*m</span><br><span class="line"></span><br><span class="line">如果内层循环改成了 m 次，时间复杂度就为 O (n*m)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int i;</span><br><span class="line"><span class="keyword">for</span>(i = <span class="number">0</span> ; i &lt; n ; i++)&#123;</span><br><span class="line">   <span class="keyword">for</span>(j = <span class="number">0</span> ; j &lt; m ; j++)&#123;</span><br><span class="line">    <span class="comment">/*时间复杂度为O(1)的程序*/</span>  </span><br><span class="line">    &#125;    </span><br><span class="line">&#125;</span><br><span class="line">类型 <span class="number">3</span>：特殊 n*n</span><br><span class="line"></span><br><span class="line">再来看一段程序，当内层循环 j = i 时</span><br><span class="line"></span><br><span class="line">int i;</span><br><span class="line"><span class="keyword">for</span>(i = <span class="number">0</span> ; i &lt; n ; i++)&#123;</span><br><span class="line">   <span class="keyword">for</span>(j = i ; j &lt; n ; j++)&#123;</span><br><span class="line">    <span class="comment">/*时间复杂度为O(1)的程序*/</span>  </span><br><span class="line">    &#125;    </span><br><span class="line">&#125;</span><br><span class="line">i = <span class="number">0</span> 时，内层循环执行了 n 次，</span><br><span class="line"></span><br><span class="line">i = <span class="number">1</span> 时，执行了 n<span class="number">-1</span> 次，</span><br><span class="line"></span><br><span class="line">i = n<span class="number">-1</span> 时，执行了 <span class="number">1</span> 次，所以总的执行次数为：</span><br><span class="line"></span><br><span class="line">n+(n<span class="number">-1</span>)+(n<span class="number">-1</span>)+...+<span class="number">1</span> = n(n+<span class="number">1</span>)/<span class="number">2</span> = n^<span class="number">2</span>^<span class="regexp">/2 + n/</span><span class="number">2</span></span><br><span class="line"></span><br><span class="line">根据大 O 推导方法，保留最高阶项，n^<span class="number">2</span>^<span class="regexp">/2 ，然后去掉这个项相乘的常数，1/</span><span class="number">2</span></span><br><span class="line"></span><br><span class="line">因此，这段代码的时间复杂度为 O (n^<span class="number">2</span>^)</span><br><span class="line"></span><br><span class="line">类型 <span class="number">4</span>：斐波那契数列</span><br><span class="line"></span><br><span class="line">long aFunc(int n) &#123;</span><br><span class="line">    <span class="keyword">if</span> (n &lt;= <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> aFunc(n - <span class="number">1</span>) + aFunc(n - <span class="number">2</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">显然运行次数，T (<span class="number">0</span>) = T (<span class="number">1</span>) = <span class="number">1</span>，同时 T (n) = T (n - <span class="number">1</span>) + T (n - <span class="number">2</span>) + <span class="number">1</span>，这里的 <span class="number">1</span> 是其中的加法算一次执行。</span><br><span class="line"></span><br><span class="line">通过归纳证明法可以证明，当 n &gt;= <span class="number">1</span> 时 T (n) &lt; (<span class="number">5</span>/<span class="number">3</span>)^n^，同时当 n &gt; <span class="number">4</span> 时 T (n) &gt;= (<span class="number">3</span>/<span class="number">2</span>)^n。</span><br><span class="line"></span><br><span class="line">简化后为 O (<span class="number">2</span>^n^)</span><br><span class="line"></span><br><span class="line">常见的时间复杂度</span><br><span class="line"></span><br><span class="line">执行次数函数	阶	术语描述</span><br><span class="line"><span class="number">12</span>	O(<span class="number">1</span>)	常数阶</span><br><span class="line"><span class="number">2</span>n+<span class="number">3</span>	O(n)	线性阶</span><br><span class="line"><span class="number">3</span>n^<span class="number">2</span>^+<span class="number">2</span>n+<span class="number">1</span>	O(n^<span class="number">2</span>^)	平方阶</span><br><span class="line"><span class="number">5</span>log2^n^+<span class="number">20</span>	O(log2^n^)	对数阶</span><br><span class="line"><span class="number">2</span>n+<span class="number">3</span>nlog2^n^+<span class="number">19</span>	O(nlogn)	nlog2^n^ 阶</span><br><span class="line"><span class="number">6</span>n^<span class="number">3</span>^+<span class="number">2</span>n^<span class="number">2</span>^+<span class="number">3</span>n+<span class="number">4</span>	O(n3)	立方阶</span><br><span class="line"><span class="number">2</span>n	O(<span class="number">2</span>n)	指数阶</span><br><span class="line">时间复杂度所耗费的时间是：</span><br><span class="line"></span><br><span class="line">O(<span class="number">1</span>) &lt; O(logn) &lt; O(n) &lt; O(nlogn) &lt; O(n^<span class="number">2</span>^) &lt; O(n^<span class="number">3</span>^) &lt;O(<span class="number">2</span>^n^) &lt; O(n!) &lt;O(n^n^)</span><br></pre></td></tr></table></figure>
<h3 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//测试调用</span></span><br><span class="line">public <span class="function"><span class="keyword">function</span> <span class="title">aa</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    $ad = [<span class="number">12</span>,<span class="number">5</span>,<span class="number">644</span>,<span class="number">64</span>,<span class="number">6546</span>,<span class="number">54</span>,<span class="number">54</span>,<span class="number">897</span>,<span class="number">321</span>,<span class="number">231</span>,<span class="number">54</span>,<span class="number">321</span>,<span class="number">56</span>];</span><br><span class="line">    $res = $<span class="keyword">this</span>-&gt;InsertSort($ad);</span><br><span class="line">    <span class="keyword">return</span> $res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> *@func 插入排序</span></span><br><span class="line"><span class="comment"> * @describe 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。</span></span><br><span class="line"><span class="comment"> * 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，</span></span><br><span class="line"><span class="comment"> * 但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。</span></span><br><span class="line"><span class="comment"> * 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * @author vio</span></span><br><span class="line"><span class="comment"> **/</span></span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">InsertSort</span>(<span class="params">array $arr=[]</span>)</span>&#123;</span><br><span class="line">    $count = count($arr);</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">1</span>;$i&lt;$count;$i++)&#123;</span><br><span class="line">        $t = $arr[$i];</span><br><span class="line">        $j = $i<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">while</span> ($j&gt;=<span class="number">0</span> &amp;&amp; $arr[$j]&gt;$t)&#123;</span><br><span class="line">            $arr[$j+<span class="number">1</span>] = $arr[$j];</span><br><span class="line">            $j--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ($i!=$j+<span class="number">1</span>)&#123;</span><br><span class="line">            $arr[$j+<span class="number">1</span>] = $t;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $arr;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> *@func 选择排序</span></span><br><span class="line"><span class="comment"> * @O    O(n^2)</span></span><br><span class="line"><span class="comment"> * @describe 遍历数组，将数组中最小的值换到第一个，然后再遍历数组，将第二小的值换到数组的第二个位置，以此类推</span></span><br><span class="line"><span class="comment"> * @author vio</span></span><br><span class="line"><span class="comment"> **/</span></span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">SelectSort</span>(<span class="params">array $arr=[]</span>)</span>&#123;</span><br><span class="line">    $count = count($arr);</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span>;$i&lt;$count;$i++)&#123;</span><br><span class="line">        $k = $i;</span><br><span class="line">        <span class="keyword">for</span>($j=$i+<span class="number">1</span>;$j&lt;$count;$j++)&#123;</span><br><span class="line">            <span class="keyword">if</span> ($arr[$j]&lt;$arr[$k])&#123;</span><br><span class="line">                $k = $j;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ($k!=$i)&#123;</span><br><span class="line">            $t = $arr[$k];</span><br><span class="line">            $arr[$k] = $arr[$i];</span><br><span class="line">            $arr[$i] = $t;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $arr;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> *@func 冒泡排序</span></span><br><span class="line"><span class="comment"> * @describe 将数组的每一个数与其后的每一个数比较，如果这个数大于他后面的数，则交换位置</span></span><br><span class="line"><span class="comment"> * @author vio</span></span><br><span class="line"><span class="comment"> **/</span></span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">BubbleSort</span>(<span class="params">array $arr=[]</span>)</span>&#123;</span><br><span class="line">    $count = count($arr);</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span>;$i&lt;$count<span class="number">-1</span>;$i++)&#123;</span><br><span class="line">        <span class="keyword">for</span> ($j=$i;$j&lt;$count;$j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>($arr[$i]&gt;$arr[$j])&#123;</span><br><span class="line">                $t = $arr[$i];</span><br><span class="line">                $arr[$i] = $arr[$j];</span><br><span class="line">                $arr[$j] = $t;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $arr;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> *@func 快速排序</span></span><br><span class="line"><span class="comment"> * @O    O(nlogn) 最糟 O(n^2)</span></span><br><span class="line"><span class="comment"> * @describe 从数组中选一个基准点，遍历数组，大于基准点的放到一个数组，其余放到另一个数组。</span></span><br><span class="line"><span class="comment"> *      递归的对子数组排序</span></span><br><span class="line"><span class="comment"> * @author vio</span></span><br><span class="line"><span class="comment">**/</span></span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">QuickSort</span>(<span class="params">array $arr=[]</span>)</span>&#123;</span><br><span class="line">    $count = count($arr);</span><br><span class="line">    <span class="keyword">if</span> ($count&lt;=<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> $arr;</span><br><span class="line">    &#125;</span><br><span class="line">    $pivot = $arr[<span class="number">0</span>];</span><br><span class="line">    $left = $right = [];</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">1</span>;$i&lt;$count;$i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>($arr[$i]&lt;$pivot)&#123;</span><br><span class="line">            array_push($left,$arr[$i]);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            array_push($right,$arr[$i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    $left = $<span class="keyword">this</span>-&gt;QuickSort($left);</span><br><span class="line">    $right = $<span class="keyword">this</span>-&gt;QuickSort($right);</span><br><span class="line">    <span class="keyword">return</span> array_merge($left,[$pivot],$right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="两数之和"><a href="#两数之和" class="headerlink" title="两数之和"></a>两数之和</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">给定 $nums = [<span class="number">2</span>, <span class="number">7</span>, <span class="number">11</span>, <span class="number">15</span>], $target = <span class="number">9</span></span><br><span class="line"></span><br><span class="line">因为 nums[<span class="number">0</span>] + nums[<span class="number">1</span>] = <span class="number">2</span> + <span class="number">7</span> = <span class="number">9</span></span><br><span class="line">所以返回 [<span class="number">0</span>, <span class="number">1</span>]</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">twoSum</span>(<span class="params">$nums, $target</span>) </span>&#123;</span><br><span class="line">    foreach($nums <span class="keyword">as</span> $k=&gt;$v)&#123;</span><br><span class="line">        $an = $target - $nums[$k];</span><br><span class="line">        unset($nums[$k]);</span><br><span class="line">        $res = array_search($an,$nums);</span><br><span class="line">            <span class="keyword">if</span>($res !== <span class="literal">false</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> [$k,$res];</span><br><span class="line">            &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">$arr = twoSum($nums,$target);</span><br><span class="line">print_r($arr);</span><br><span class="line"> <span class="function"><span class="keyword">function</span> <span class="title">twoSum</span>(<span class="params">$nums, $target</span>) </span>&#123;</span><br><span class="line">        $res = [];</span><br><span class="line">        foreach($nums <span class="keyword">as</span> $k =&gt; $v) &#123;</span><br><span class="line">            $diff = $target - $v;</span><br><span class="line">            <span class="keyword">if</span>(in_array($diff, $nums)) &#123;</span><br><span class="line">                $diff_key = array_search($diff, $nums);</span><br><span class="line">                <span class="keyword">if</span>($diff_key !== $k) &#123;</span><br><span class="line">                    $res = [$k, $diff_key];</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> $res;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">twosum</span>（<span class="title">$nums</span>，<span class="title">$target</span>）</span>&#123;</span><br><span class="line">    $count=count（$nums）；</span><br><span class="line">    <span class="keyword">for</span>（$K=<span class="number">0</span>；k&lt;$count；$k++）&#123;</span><br><span class="line">    <span class="keyword">for</span>（$i=<span class="number">0</span>；$i&lt;$count；$i++）&#123;</span><br><span class="line">    <span class="keyword">if</span>（$k&lt;$i&amp;&amp;$nums[$i]+$nums[$k]==$target）&#123;</span><br><span class="line">    <span class="keyword">return</span>[$k，$i]；</span><br><span class="line">    &#125;&#125;</span><br><span class="line">    <span class="keyword">return</span>[]；</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">twosum</span>（<span class="title">$nums</span>，<span class="title">$target</span>）</span>&#123;</span><br><span class="line">    $numsMatches=[]；</span><br><span class="line">    foreach（$nums <span class="keyword">as</span> $k=&gt;$v）&#123;</span><br><span class="line">    $numsMatches[$target-$v]=$k;</span><br><span class="line">    &#125;</span><br><span class="line">    foreach（$nums <span class="keyword">as</span> k=&gt;$v）&#123;</span><br><span class="line">    <span class="keyword">if</span>（isset（$numsMatches[$v]）&amp;&amp; $K!=$numsMatches[$v]）&#123;</span><br><span class="line">    <span class="keyword">return</span>[$k，$numsMatches[$v]]；</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>[]；</span><br><span class="line">    </span><br><span class="line">    https:<span class="comment">//learnku.com/articles/31920 https://learnku.com/php/tweets/31775</span></span><br></pre></td></tr></table></figure>
<h3 id="索引顺序查找"><a href="#索引顺序查找" class="headerlink" title="索引顺序查找"></a>索引顺序查找</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Index</span></span>&#123;</span><br><span class="line">    public $key;<span class="comment">//索引块表中的最大值</span></span><br><span class="line">    public $start;<span class="comment">//索引块表中的起始地址</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">cmp</span>(<span class="params">Index $a,Index $b</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($a-&gt;key==$b-&gt;start)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $a-&gt;key&gt;$b-&gt;key?<span class="number">1</span>:<span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">从索引表中检索，再从数据集合里检索数据</span></span><br><span class="line"><span class="comment">**/</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">search</span>(<span class="params">$key,$data=[],$index=[]</span>):<span class="title">int</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $i=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>($i&lt;<span class="number">3</span>&amp;&amp;$key&gt;$index[$i]-&gt;key)&#123;<span class="comment">//索引表中检索获取某块</span></span><br><span class="line">        $i++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> ($i&gt;=<span class="number">3</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    $startValue = $index[$i]-&gt;start;<span class="comment">//获取某块起始地址</span></span><br><span class="line">    <span class="keyword">while</span>($startValue&lt;=$startValue+<span class="number">5</span>&amp;&amp;$data[$startValue]!=$key)&#123;<span class="comment">//从查找表指定范围检索</span></span><br><span class="line">        $startValue++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> ($startValue&gt;$startValue+<span class="number">5</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $startValue;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">(<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查找表【数据集合】</span></span><br><span class="line">    $data = [<span class="number">54</span>,<span class="number">53</span>,<span class="number">52</span>,<span class="number">51</span>,<span class="number">50</span>,<span class="number">55</span>, <span class="number">44</span>,<span class="number">46</span>,<span class="number">48</span>,<span class="number">49</span>,<span class="number">43</span>,<span class="number">41</span>, <span class="number">84</span>,<span class="number">83</span>,<span class="number">65</span>,<span class="number">74</span>,<span class="number">98</span>,<span class="number">100</span>];</span><br><span class="line">    <span class="comment">//索引块表</span></span><br><span class="line">    $index = [];</span><br><span class="line">    $j=<span class="number">-1</span>;</span><br><span class="line">    $indexObj = <span class="keyword">new</span> Index();</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span>;$i&lt;<span class="number">3</span>;$i++)&#123;<span class="comment">//数据分块处理</span></span><br><span class="line">        $obj = clone $indexObj;</span><br><span class="line">        $obj-&gt;start=$j+<span class="number">1</span>;</span><br><span class="line">        $j+=<span class="number">6</span>;</span><br><span class="line">        $index[$i] = $obj;</span><br><span class="line">        <span class="keyword">for</span> ($k=$index[$i]-&gt;start;$k&lt;=$j;$k++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> ($index[$i]-&gt;key&lt;$data[$k])&#123;</span><br><span class="line">                $index[$i]-&gt;key = $data[$k];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    usort($index,<span class="string">'cmp'</span>);</span><br><span class="line">    $key = fgets(STDIN,<span class="number">10</span>);</span><br><span class="line">    $location = search(intval($key),$data,$index);</span><br><span class="line">    <span class="keyword">if</span> ($location&gt;=<span class="number">0</span>)&#123;</span><br><span class="line">        fwrite(STDOUT,<span class="string">"ok find elem "</span>.$location);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        fwrite(STDERR,<span class="string">"not found!"</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;)();</span><br><span class="line">https:<span class="comment">//learnku.com/articles/31876</span></span><br></pre></td></tr></table></figure>
<h3 id="数据结构栈和队列排队算法"><a href="#数据结构栈和队列排队算法" class="headerlink" title="数据结构栈和队列排队算法"></a>数据结构栈和队列排队算法</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br></pre></td><td class="code"><pre><span class="line">栈也是一种特殊的线性表结构，数据只能在某一端进行操作，能操作数据的那一端为栈顶，对应的为栈底，数据入栈的过程就是入栈【压栈，进栈】，数据出栈的过程就是【弹栈，出栈】，遵循先进后出原则 FIRST IN LAST OUT 即 FILO 结构，基于连续的内存单元则是顺序栈表，一种是使用分散的内存单元存储为链式结构即链栈结构。</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 队列+栈数据结构的停车排队管理系统</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">define(<span class="string">"MAXSIZE"</span>,<span class="number">3</span>);</span><br><span class="line">$station   = [];<span class="comment">//停车场栈</span></span><br><span class="line">$parkTop   = <span class="number">0</span>;</span><br><span class="line">$road      = [];<span class="comment">//便道队列</span></span><br><span class="line">$roadFront = $roadNear = <span class="number">0</span>;<span class="comment">//队列游标</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Car</span></span></span><br><span class="line"><span class="class"></span>&#123;</span><br><span class="line">    public $carNumber;</span><br><span class="line">    public $arriveTime;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 压栈</span></span><br><span class="line"><span class="comment"> * @param $station</span></span><br><span class="line"><span class="comment"> * @param $parkTop</span></span><br><span class="line"><span class="comment"> * @param Car $car</span></span><br><span class="line"><span class="comment"> * @return int</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">push</span>(<span class="params">&amp;$station,&amp;$parkTop,Car $car</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($parkTop&gt;=MAXSIZE)&#123;</span><br><span class="line">        echo <span class="string">"停车场没有位置了哦"</span>.PHP_EOL;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    $station[$parkTop] = $car;</span><br><span class="line">    echo <span class="string">"车牌号为:"</span>.$car-&gt;carNumber.<span class="string">"的车主停车位为："</span>.($parkTop+<span class="number">1</span>).PHP_EOL;</span><br><span class="line">    $parkTop++;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 出栈</span></span><br><span class="line"><span class="comment"> * @param $station</span></span><br><span class="line"><span class="comment"> * @param $parkTop</span></span><br><span class="line"><span class="comment"> * @param $carNumber</span></span><br><span class="line"><span class="comment"> * @return Car</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">pop</span>(<span class="params">&amp;$station,&amp;$parkTop,$carNumber</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $location        = <span class="number">-1</span>;</span><br><span class="line">    $tempStation     = [];<span class="comment">//临时栈</span></span><br><span class="line">    $tempLocation    = <span class="number">0</span>;</span><br><span class="line">    $car             = <span class="keyword">new</span> Car();</span><br><span class="line">    $car-&gt;carNumber  = <span class="number">-1</span>;</span><br><span class="line">    $car-&gt;arriveTime = <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">0</span>;$i&lt;$parkTop;$i++)&#123;</span><br><span class="line">        <span class="keyword">if</span> ($station[$i]-&gt;carNumber==$carNumber)&#123;</span><br><span class="line">            $location=$i;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> ($location==<span class="number">-1</span>)&#123;</span><br><span class="line">        echo <span class="string">"停车场没有这车"</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">while</span>($parkTop&gt;$location+<span class="number">1</span>)&#123;</span><br><span class="line">            $parkTop--;</span><br><span class="line">            $tempStation[$tempLocation] = $station[$parkTop];</span><br><span class="line">            $tempLocation++;</span><br><span class="line">        &#125;</span><br><span class="line">        $parkTop--;</span><br><span class="line">        $car = $station[$parkTop];</span><br><span class="line">        <span class="keyword">while</span>($tempLocation&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            $tempLocation--;</span><br><span class="line">            $station[$parkTop] = $tempStation[$tempLocation];</span><br><span class="line">            $parkTop++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> $car;</span><br><span class="line">&#125;</span><br><span class="line">echo <span class="string">"欢迎使用停车位管理系统"</span>.PHP_EOL;</span><br><span class="line">echo date(<span class="string">"Y年-m月-d日 H时:i分:s秒"</span>).PHP_EOL;</span><br><span class="line"><span class="keyword">while</span>(<span class="number">1</span>)&#123;</span><br><span class="line"></span><br><span class="line">    echo <span class="string">"停车(A;离开(D;是否有空位(E;停车场车辆列表(L;退出#"</span>.PHP_EOL;</span><br><span class="line">    $cmd = fread(STDIN,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">if</span> ($cmd==<span class="string">'#'</span>)&#123;</span><br><span class="line">        echo <span class="string">"欢迎下次再来"</span>.PHP_EOL;</span><br><span class="line">        <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">switch</span> (trim($cmd))&#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">'L'</span>:</span><br><span class="line">            <span class="keyword">if</span> ($parkTop&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                echo <span class="string">"|---车牌号---|---停车时间---|---车 位---|---区域---|"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">for</span>($j=$parkTop<span class="number">-1</span>;$j&gt;=<span class="number">0</span>;$j--)&#123;</span><br><span class="line">                    echo <span class="string">"|---"</span>.$station[$j]-&gt;carNumber.<span class="string">"---|---"</span>.$station[$j]-&gt;arriveTime.<span class="string">":00:00---|---"</span>.($j+<span class="number">1</span>).<span class="string">' 号---|---车场---|'</span>.PHP_EOL;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> ($roadFront!=$roadNear)&#123;</span><br><span class="line">                <span class="keyword">for</span>($j=$roadFront;$j&lt;$roadNear;$j++)&#123;</span><br><span class="line">                    echo <span class="string">"|---"</span>.$road[$j]-&gt;carNumber.<span class="string">"---|---"</span>.$road[$j]-&gt;arriveTime.<span class="string">":00:00---|---"</span>.($j+<span class="number">1</span>).<span class="string">' 号---|---便道---|'</span>.PHP_EOL;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">"A"</span>:</span><br><span class="line">            echo <span class="string">"请输入车牌号和到达时间"</span>.PHP_EOL;</span><br><span class="line">            $input = trim(fread(STDIN,<span class="number">10</span>));</span><br><span class="line">            fflush(STDIN);</span><br><span class="line">            <span class="keyword">if</span> (strpos($input,<span class="string">":"</span>)&lt;<span class="number">-1</span>)&#123;</span><br><span class="line">                echo <span class="string">"输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            $input = explode(<span class="string">":"</span>,$input);</span><br><span class="line">            <span class="keyword">if</span> (count($input)&lt;<span class="number">2</span>)&#123;</span><br><span class="line">                echo <span class="string">"车牌号和时间输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            $carNumber = $input[<span class="number">0</span>];</span><br><span class="line">            $arriveTime= (integer)$input[<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span> (empty($arriveTime))&#123;</span><br><span class="line">                echo <span class="string">"时间输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            $car = <span class="keyword">new</span> Car();</span><br><span class="line">            $car-&gt;carNumber = $carNumber;</span><br><span class="line">            $car-&gt;arriveTime = $arriveTime;</span><br><span class="line">            $result = push($station,$parkTop,$car);</span><br><span class="line">            <span class="keyword">if</span> ($result==<span class="number">-1</span>)&#123;</span><br><span class="line">                $road[$roadNear] = $car;</span><br><span class="line">                $roadNear++;</span><br><span class="line">                echo <span class="string">"车牌为号："</span>.$car-&gt;carNumber.<span class="string">"的车停在了便道上的:"</span>.$roadNear.<span class="string">"，位置上了"</span>.PHP_EOL;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">"E"</span>:</span><br><span class="line">            <span class="keyword">if</span> ($parkTop&gt;=MAXSIZE)&#123;</span><br><span class="line">                echo <span class="string">"目前没有空位了，进来只能停在便道上了"</span>.PHP_EOL;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                echo <span class="string">"有空位，停车费一个小时20美金"</span>.PHP_EOL;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">"D"</span>:</span><br><span class="line">            echo <span class="string">"请输入要离开的车牌号和离开时间"</span>.PHP_EOL;</span><br><span class="line">            $input = trim(fread(STDIN,<span class="number">10</span>));</span><br><span class="line">            fflush(STDIN);</span><br><span class="line">            <span class="keyword">if</span> (strpos($input,<span class="string">":"</span>)&lt;<span class="number">-1</span>)&#123;</span><br><span class="line">                echo <span class="string">"输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            $input = explode(<span class="string">":"</span>,$input);</span><br><span class="line">            <span class="keyword">if</span> (count($input)&lt;<span class="number">2</span>)&#123;</span><br><span class="line">                echo <span class="string">"输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            $carNumber = $input[<span class="number">0</span>];</span><br><span class="line">            $arriveTime = $input[<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span> (empty($arriveTime))&#123;</span><br><span class="line">                echo <span class="string">"输入错误"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">/** @var Car $car */</span></span><br><span class="line">            $car = pop($station,$parkTop,$carNumber);</span><br><span class="line">            <span class="keyword">if</span> ($car-&gt;carNumber==<span class="number">-1</span>)&#123;</span><br><span class="line">                echo <span class="string">"停车场没有你要找的车"</span>.PHP_EOL;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                $time = $arriveTime-$car-&gt;arriveTime;</span><br><span class="line">                echo <span class="string">"车牌号为:"</span>.$car-&gt;carNumber.<span class="string">"的停车时间为："</span>.$time.<span class="string">"H,需要缴纳:"</span>.($time*<span class="number">20</span>).<span class="string">"美金停车费用"</span>.PHP_EOL;</span><br><span class="line">                echo <span class="string">"车牌号为:"</span>.$car-&gt;carNumber.<span class="string">"的车已经出来，停在便道上的车将进场"</span>.PHP_EOL;</span><br><span class="line">                <span class="keyword">if</span> ($roadFront!=$roadNear)&#123;</span><br><span class="line">                    $car = $road[$roadFront];</span><br><span class="line">                    echo <span class="string">"车牌号为："</span>.$car-&gt;carNumber.<span class="string">"的车请输入到达时间"</span>.PHP_EOL;</span><br><span class="line">                    $arriveTime = trim(fread(STDIN,<span class="number">5</span>));</span><br><span class="line">                    $car-&gt;arriveTime = $arriveTime;</span><br><span class="line">                    $station[$parkTop] = $car;</span><br><span class="line">                    $parkTop++;</span><br><span class="line">                    $roadFront++;</span><br><span class="line">                    echo <span class="string">"停在便道上的车牌为："</span>.$car-&gt;carNumber.<span class="string">"已经进入停车场了"</span>.PHP_EOL;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;https:<span class="comment">//learnku.com/articles/30492</span></span><br></pre></td></tr></table></figure>
<h3 id="队列数据结构"><a href="#队列数据结构" class="headerlink" title="队列数据结构"></a>队列数据结构</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line">define(<span class="string">'MAXSIZE'</span>,<span class="number">5</span>);<span class="comment">//队列空间大小</span></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @param $queue 队列存储空间</span></span><br><span class="line"><span class="comment"> * @param $front 队列队头游标</span></span><br><span class="line"><span class="comment"> * @param $near  队列队尾游标</span></span><br><span class="line"><span class="comment"> * @param $data  进队的数据</span></span><br><span class="line"><span class="comment"> * @return int</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">enQueue</span>(<span class="params">&amp;$queue,$front,$near,$data</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (($near+<span class="number">1</span>)%MAXSIZE==$front)&#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"队空间已满"</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    $queue[$near%MAXSIZE] = $data;</span><br><span class="line">    $near+=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> $near;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 出队操作</span></span><br><span class="line"><span class="comment"> * @param $queue</span></span><br><span class="line"><span class="comment"> * @param $front</span></span><br><span class="line"><span class="comment"> * @param $near</span></span><br><span class="line"><span class="comment"> * @return int</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">deQueue</span>(<span class="params">&amp;$queue,$front,$near</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ($front==$near%MAXSIZE)&#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"空队列"</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    $data = $queue[$front];</span><br><span class="line">    echo <span class="string">"出队元素："</span>.$data.PHP_EOL;</span><br><span class="line">    $front = ($front+<span class="number">1</span>)%MAXSIZE;</span><br><span class="line">    <span class="keyword">return</span> $front;</span><br><span class="line">&#125;</span><br><span class="line">$a = [];<span class="comment">//队列 使用数组模拟</span></span><br><span class="line">$front = $near = <span class="number">0</span>;<span class="comment">//游标初始化</span></span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">1</span>);</span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">2</span>);</span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">3</span>);</span><br><span class="line"></span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line"><span class="comment">//$front = deQueue($a,$front,$near);</span></span><br><span class="line"></span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">100</span>);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line"></span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">1</span>);</span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">2</span>);</span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">3</span>);</span><br><span class="line">$near = enQueue($a,$front,$near,<span class="number">4</span>);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">$front = deQueue($a,$front,$near);</span><br><span class="line">https:<span class="comment">//learnku.com/articles/30430</span></span><br></pre></td></tr></table></figure>
<h3 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Elem</span></span>&#123;</span><br><span class="line">    public $key;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Table</span></span></span><br><span class="line"><span class="class"></span>&#123;</span><br><span class="line">    public $data = [];</span><br><span class="line">    public $lenght;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">createTable</span>(<span class="params">Table &amp;$table,$length</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $table-&gt;lenght = $length;</span><br><span class="line">    $obj = <span class="keyword">new</span> Elem();</span><br><span class="line">    fwrite(STDOUT,<span class="string">"请输入数据：\n"</span>);</span><br><span class="line">    <span class="keyword">for</span>($i=<span class="number">1</span>;$i&lt;=$table-&gt;lenght;$i++)&#123;</span><br><span class="line">        $elem = clone $obj;</span><br><span class="line">        $elem-&gt;key = fgets(STDIN,<span class="number">10</span>);</span><br><span class="line">        $table-&gt;data[$i] = $elem;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">searchBin</span>(<span class="params">Table $table,$key</span>):<span class="title">int</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $low = <span class="number">1</span>;</span><br><span class="line">    $height = $table-&gt;lenght;</span><br><span class="line">    <span class="keyword">while</span>($low&lt;=$height)&#123;</span><br><span class="line">        $mid = floor(($low+intval($height))/<span class="number">2</span>);</span><br><span class="line">        <span class="keyword">if</span> ($table-&gt;data[$mid]-&gt;key==$key)&#123;</span><br><span class="line">            <span class="keyword">return</span> $mid;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>($table-&gt;data[$mid]-&gt;key&gt;$key)&#123;</span><br><span class="line">            $height=$mid<span class="number">-1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            $low = $mid+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line">(<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    $table = <span class="keyword">new</span> Table();</span><br><span class="line">    fwrite(STDOUT,<span class="string">"请输入数据元素个数：\n"</span>);</span><br><span class="line">    $length = fgets(STDIN,<span class="number">10</span>);</span><br><span class="line">    createTable($table,$length);</span><br><span class="line">    fwrite(STDOUT,<span class="string">"请输入要查找的数据元素：\n"</span>);</span><br><span class="line">    $key = (integer)fgets(STDIN,<span class="number">10</span>);</span><br><span class="line">    $location = searchBin($table,$key);</span><br><span class="line">    <span class="keyword">if</span> ($location)&#123;</span><br><span class="line">        fwrite(STDOUT,<span class="string">"查找到的数据索引为：$location\n"</span>);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        fwrite(STDERR,<span class="string">"查找不到指定的内容\n"</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;)();https:<span class="comment">//learnku.com/articles/31829</span></span><br></pre></td></tr></table></figure>
<h3 id="约瑟夫环"><a href="#约瑟夫环" class="headerlink" title="约瑟夫环"></a>约瑟夫环</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line">一群猴子排成一圈，按 <span class="number">1</span>，<span class="number">2</span>，…，n 依次编号。然后从第 <span class="number">1</span> 只开始数，数到第 m 只，把它踢出圈，从它后面再开始数，再数到第 m 只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入 m、n, 输出最后那个大王的编号。</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">king</span>(<span class="params">$n, $m</span>)</span>&#123;</span><br><span class="line">        <span class="comment">//创建1到n数组</span></span><br><span class="line">        $monkeys = range(<span class="number">1</span>, $n);</span><br><span class="line">        $i=<span class="number">0</span>;</span><br><span class="line">        <span class="comment">//循环条件为猴子数量大于1</span></span><br><span class="line">        <span class="keyword">while</span> (count($monkeys)&gt;<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="comment">//$i为数组下标;$i+1为猴子标号</span></span><br><span class="line">            <span class="keyword">if</span>(($i+<span class="number">1</span>)%$m==<span class="number">0</span>) &#123;</span><br><span class="line">                <span class="comment">//余数等于0表示正好第m个，删除，用unset删除保持下标关系</span></span><br><span class="line">                unset($monkeys[$i]);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//如果余数不等于0，则把数组下标为$i的放最后，形成一个圆形结构</span></span><br><span class="line">                array_push($monkeys,$monkeys[$i]);</span><br><span class="line"></span><br><span class="line">                unset($monkeys[$i]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//$i 循环+1，不断把猴子删除，或 push到数组</span></span><br><span class="line">            $i++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//猴子数量等于1时输出猴子标号，得出猴王</span></span><br><span class="line">        <span class="keyword">return</span> current($monkeys);</span><br><span class="line">    &#125;</span><br><span class="line">    echo king(<span class="number">6</span>,<span class="number">3</span>);</span><br><span class="line">range(m,n) 创建一个包含从 <span class="string">"m"</span> 到 <span class="string">"n"</span> 之间的元素范围的数组</span><br><span class="line">range(<span class="number">1</span>, <span class="number">5</span>);</span><br><span class="line"><span class="comment">// [0=&gt;1, 1=&gt;2, 2=&gt;3, 3=&gt;4, 4=&gt;5];</span></span><br><span class="line">unset(...$str) 销毁给定的变量</span><br><span class="line">$array=[<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>];</span><br><span class="line">unset($array[<span class="number">2</span>]);</span><br><span class="line"><span class="comment">// [0=&gt;1, 1=&gt;2, 3=&gt;4, 4=&gt;5];</span></span><br><span class="line">array_push($array, ...$str) 向数组尾部插入变量</span><br><span class="line">$array=[<span class="number">1</span>, <span class="number">2</span>];</span><br><span class="line">array_push($array, <span class="number">3</span>, <span class="number">4</span>);</span><br><span class="line"><span class="comment">// [1, 2, 3, 4 ];</span></span><br><span class="line">current() 输出数组中的当前元素的值</span><br><span class="line">end() - 将内部指针指向数组中的最后一个元素，并输出</span><br><span class="line">next() - 将内部指针指向数组中的下一个元素，并输出</span><br><span class="line">prev() - 将内部指针指向数组中的上一个元素，并输出</span><br><span class="line">reset() - 将内部指针指向数组中的第一个元素，并输出</span><br><span class="line">each() - 返回当前元素的键名和键值，并将内部指针向前移动 </span><br><span class="line">https:<span class="comment">//learnku.com/articles/33253</span></span><br></pre></td></tr></table></figure>
<h3 id="TwoSum"><a href="#TwoSum" class="headerlink" title="TwoSum"></a>TwoSum</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">func TwoSum1(nums []int, target int) []int &#123;</span><br><span class="line">    len := len(nums)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; len; i++ &#123;</span><br><span class="line">        <span class="keyword">for</span> j := i + <span class="number">1</span>; j &lt; len; j++ &#123;</span><br><span class="line">            <span class="keyword">if</span> target == nums[i]+nums[j] &#123;</span><br><span class="line">                <span class="keyword">return</span> []int&#123;i, j&#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> nil</span><br><span class="line">&#125;</span><br><span class="line">a + b = target 转换成 b = target - a，将值与下标的关系存入map中</span><br><span class="line">func TwoSum2(nums []int, target int) []int &#123;</span><br><span class="line">    aMap := make(map[int]int, len(nums))</span><br><span class="line"></span><br><span class="line">    <span class="comment">//循环nums 获取 key and value</span></span><br><span class="line">    <span class="keyword">for</span> k, <span class="attr">v</span> := range nums &#123;</span><br><span class="line">        aMap[v] = k</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> j, <span class="attr">ok</span> := aMap[target-v]; ok &#123;</span><br><span class="line">            <span class="comment">//从值与键的映射中查询 成功查询说明 j 之前 有值 满足条件  注意：此时 j&lt;k  先建映射再进行查询</span></span><br><span class="line">            <span class="keyword">return</span> []int&#123;j, k&#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> nil</span><br><span class="line">&#125;</span><br><span class="line">https:<span class="comment">//dalebao.github.io/2019/04/13/LeetCode-001-TwoSum/</span></span><br></pre></td></tr></table></figure>
<h3 id="二分查找-1"><a href="#二分查找-1" class="headerlink" title="二分查找"></a>二分查找</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">binarySerach</span>(<span class="params">$data, $res</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">        $left  = <span class="number">0</span>;</span><br><span class="line">        $right = count($data) - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> ($left &lt;= $right) &#123;</span><br><span class="line">            $middle = $left + (($right - $left) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">            <span class="keyword">if</span> ($data[$middle] == $res) <span class="keyword">return</span> $middle;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> ($data[$middle] &gt; $res) $right = $middle - <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span> $left = $middle + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> 题目让我们找出重复的数，给定的数组的值都在 <span class="number">1</span>-n 之间，数组总数是 n+<span class="number">1</span>, 那么必然有数字是重复的，让我们来找出这个重复的数。</span><br><span class="line"> 这道题可以有更好的解法 (我这里强行把它当做二分的场景)，二分的解题思路就是取 n 的中位数，遍历数组，统计不大于中位数的个数，如果不大于中位数的个数比中位数还大，说明重复的数在中位数的左边 (注意包括中位数自己，理解一下这一句)，否则的话重复的数肯定出现在中位数的右边，而且肯定不包括中位数。好了下面看代码再细讲。</span><br><span class="line"> </span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * @param Integer[] $nums</span></span><br><span class="line"><span class="comment">     * @return Integer</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">findDuplicate</span>(<span class="params">$nums</span>) </span>&#123;</span><br><span class="line">        $left = <span class="number">1</span>;</span><br><span class="line">        $right = count($nums) - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> ($left &lt; $right) &#123;  <span class="comment">// &lt;</span></span><br><span class="line">            $middle = ($left + $right) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">            $sum = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> ($j = <span class="number">0</span>; $j &lt; count($nums); $j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> ($nums[$j] &lt;= $middle) &#123;</span><br><span class="line">                    $sum++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> ($sum &lt;= $middle) &#123;  <span class="comment">//排除掉中位数</span></span><br><span class="line">                $left = $middle + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;   <span class="comment">//不能排除中位数</span></span><br><span class="line">                 $right = $middle;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//相返回left还是right都可以  因为必然存在left==right</span></span><br><span class="line">        <span class="keyword">return</span> $left;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<h3 id="二分查找法"><a href="#二分查找法" class="headerlink" title="二分查找法"></a>二分查找法</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">所谓二分查找，针对的是一个有序的数据集合（这点很重要），查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 <span class="number">0</span>。注意到二分查找针对的必须是已经排序过的有序数组，否则不能使用该算法。</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">binary_search</span>(<span class="params">$nums, $num</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> binary_search_internal($nums, $num, <span class="number">0</span>, count($nums) - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">binary_search_internal</span>(<span class="params">$nums, $num, $low, $high</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> ($low &gt; $high) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        $mid = floor(($low + $high) / <span class="number">2</span>);</span><br><span class="line">        <span class="keyword">if</span> ($num &gt; $nums[$mid]) &#123;</span><br><span class="line">            <span class="keyword">return</span> binary_search_internal($nums, $num, $mid + <span class="number">1</span>, $high);</span><br><span class="line">        &#125; elseif ($num &lt; $nums[$mid]) &#123;</span><br><span class="line">            <span class="keyword">return</span> binary_search_internal($nums, $num, $low, $mid - <span class="number">1</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> $mid;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    $nums = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>];</span><br><span class="line">    $index = binary_search($nums, <span class="number">5</span>);</span><br><span class="line">    print $index;</span><br><span class="line">    https:<span class="comment">//learnku.com/articles/37822</span></span><br><span class="line">    使用二分查找需要注意一个前提，那就是针对有序数组，换言之，二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，因此，这种情况下就不适用二分查找了，比如我们的数据库查询，增删改查很频繁，显然不是通过二分查找来进行查询的。</span><br></pre></td></tr></table></figure>
<h3 id="对称括号"><a href="#对称括号" class="headerlink" title="对称括号"></a>对称括号</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">isValid</span>(<span class="params">$s</span>) </span>&#123;</span><br><span class="line">        $s = str_replace([<span class="string">'()'</span>, <span class="string">'[]'</span>, <span class="string">'&#123;&#125;'</span>], <span class="string">''</span>, $s, $count);</span><br><span class="line">        <span class="keyword">if</span>($count == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> strlen($s)==<span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> $<span class="keyword">this</span>-&gt;isValid($s);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    https:<span class="comment">//www.debuginn.cn/5081.html  https://github.com/debuginn/Learning-Code-Algorithm</span></span><br></pre></td></tr></table></figure>
<h3 id="无限级菜单"><a href="#无限级菜单" class="headerlink" title="无限级菜单"></a>无限级菜单</h3><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line">CREATE TABLE <span class="string">`SuperUserMenus`</span> (</span><br><span class="line">  <span class="string">`id`</span> int(<span class="number">11</span>) NOT NULL AUTO_INCREMENT COMMENT <span class="string">'ID'</span>,</span><br><span class="line">  <span class="string">`pid`</span> int(<span class="number">11</span>) NOT NULL COMMENT <span class="string">'父级ID'</span>,</span><br><span class="line">  <span class="string">`order`</span> int(<span class="number">11</span>) NOT NULL DEFAULT <span class="string">'0'</span> COMMENT <span class="string">'菜单排序'</span>,</span><br><span class="line">  <span class="string">`title`</span> varchar(<span class="number">100</span>) NOT NULL COMMENT <span class="string">'菜单标题'</span>,</span><br><span class="line">  <span class="string">`controller`</span> varchar(<span class="number">100</span>) DEFAULT NULL COMMENT <span class="string">'控制器名称'</span>,</span><br><span class="line">  <span class="string">`method`</span> varchar(<span class="number">100</span>) DEFAULT NULL COMMENT <span class="string">'方法名称'</span>,</span><br><span class="line">  <span class="string">`ishidden`</span> int(<span class="number">1</span>) NOT NULL DEFAULT <span class="string">'0'</span> COMMENT <span class="string">'是否隐藏：0正常显示，1隐藏'</span>,</span><br><span class="line">  <span class="string">`status`</span> int(<span class="number">1</span>) NOT NULL DEFAULT <span class="string">'0'</span> COMMENT <span class="string">'状态：0正常，1禁用'</span>,</span><br><span class="line">  PRIMARY KEY (<span class="string">`id`</span>)</span><br><span class="line">) ENGINE=InnoDB DEFAULT CHARSET=utf8;</span><br><span class="line">public <span class="function"><span class="keyword">function</span> <span class="title">index</span>(<span class="params"></span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    $Super_id = <span class="number">1</span>;</span><br><span class="line">    $menus = <span class="literal">false</span>;</span><br><span class="line">    $role = Db::table(<span class="string">'SuperUser'</span>)-&gt;where(<span class="string">'Super_id'</span>, $Super_id)-&gt;select();</span><br><span class="line">    $role = $role[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">if</span> ($role) &#123;</span><br><span class="line">        $role[<span class="string">'rights'</span>] = (isset($role[<span class="string">'rights'</span>]) &amp;&amp; $role[<span class="string">'rights'</span>]) ? json_decode($role[<span class="string">'rights'</span>], <span class="literal">true</span>) : [];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> ($role[<span class="string">'rights'</span>]) &#123;</span><br><span class="line">        $menus = Db::query(<span class="string">'select * from SuperUserMenus where id in('</span> . implode(<span class="string">','</span>, $role[<span class="string">'rights'</span>]) . <span class="string">') and ishidden=0 and status=0'</span>);</span><br><span class="line">        $menus = $<span class="keyword">this</span>-&gt;_array_column($menus, <span class="literal">null</span>, <span class="string">'id'</span>);</span><br><span class="line">        $menus &amp;&amp; $menus = $<span class="keyword">this</span>-&gt;gettreeitems($menus);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> json_encode($menus);</span><br><span class="line">&#125;</span><br><span class="line">private <span class="function"><span class="keyword">function</span> <span class="title">gettreeitems</span>(<span class="params">$items</span>)</span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        $tree = array();</span><br><span class="line">        foreach ($items <span class="keyword">as</span> $item) &#123;</span><br><span class="line">            <span class="keyword">if</span> (isset($items[$item[<span class="string">'pid'</span>]])) &#123;</span><br><span class="line">                $items[$item[<span class="string">'pid'</span>]][<span class="string">'children'</span>][] = &amp;$items[$item[<span class="string">'id'</span>]];</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                $tree[] = &amp;$items[$item[<span class="string">'id'</span>]];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> $tree;</span><br><span class="line">    &#125;</span><br><span class="line">    https:<span class="comment">//www.debuginn.cn/4549.html</span></span><br></pre></td></tr></table></figure>
<p><a href="https://github.com/zhangdejian/LeetCode_PHP" target="_blank" rel="noopener">LeetCode_PHP</a></p>
<p><a href="https://learnku.com/articles/39264" target="_blank" rel="noopener">二叉树的遍历</a></p>
<p><a href="https://learnku.com/articles/38049" target="_blank" rel="noopener">两数之和</a></p>
<p><a href="https://learnku.com/articles/37750" target="_blank" rel="noopener">PHP 排序算法之选择排序</a></p>
<p><a href="http://jartto.wang/2018/11/26/algorithm3/" target="_blank" rel="noopener">算法图解3 - 递归，快排</a></p>
<p><a href="https://github.com/aliliin/LeetCode-Algorithms" target="_blank" rel="noopener">LeetCode-Algorithms 算法题 PHP 实现</a></p>
<p><a href="https://github.com/icecho/leetcode" target="_blank" rel="noopener">尝试 leetcode 题目</a></p>
<p><a href="https://www.fanhaobai.com/2017/02/reward.html" target="_blank" rel="noopener">PHP生成随机红包算法</a></p>
<p><a href="https://www.fanhaobai.com/2017/07/b-.html" target="_blank" rel="noopener">什么是B-树</a></p>
<p><a href="https://www.goozp.com/article/65.html" target="_blank" rel="noopener">数据结构的基本概念</a></p>
<p><a href="https://www.boatsky.com/blog/10" target="_blank" rel="noopener">JavaScript排序算法及性能比较</a></p>
<p><a href="https://www.einsition.com/article/16/details" target="_blank" rel="noopener">十大经典排序算法</a></p>
<p><a href="https://github.com/xx19941215/Leetcode-database-problem" target="_blank" rel="noopener">Leetcode 数据库题目</a></p>
<p><a href="https://github.com/xingshaocheng/architect-awesome" target="_blank" rel="noopener">后端架构师技术图谱</a></p>
<p><a href="https://greenlightt.github.io/2018/02/26/arithmetic-sort/" target="_blank" rel="noopener">算法之排序</a></p>
<p><a href="https://learnku.com/articles/30789" target="_blank" rel="noopener">二叉树的遍历算法</a></p>
<p><a href="https://learnku.com/articles/29685" target="_blank" rel="noopener">TCP/IP 协议低层驱动原理</a></p>
<p><a href="https://github.com/azl397985856/leetcode" target="_blank" rel="noopener"> leetcode题解</a></p>
<p><a href="https://github.com/Sneezry/leetpress" target="_blank" rel="noopener"> LeetCode 的题目印成一本书使用这个小工具： </a></p>
<p><a href="https://www.dotcpp.com/course/ds/300004.html" target="_blank" rel="noopener">数据结构入门</a></p>
<p><a href="https://learnku.com/articles/37371" target="_blank" rel="noopener">数据结构与算法分析</a></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/11/23/PHP依赖注入/" rel="next" title="PHP依赖注入">
                <i class="fa fa-chevron-left"></i> PHP依赖注入
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/11/26/浅谈php设计模式/" rel="prev" title="浅谈php设计模式">
                浅谈php设计模式 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
          <div class="comments" id="comments">
             <div id="gitment-container"></div>
         </div>
  




        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">苏生不惑</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">382</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">37</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/sushengbuhuo" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="mysusheng@gmail.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://plus.google.com/mysusheng" target="_blank" title="Google">
                      
                        <i class="fa fa-fw fa-google"></i>Google</a>
                  </span>
                
            </div>
          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-block">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                Links
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://v2ex.com/" title="v2ex" target="_blank">v2ex</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.fanhaobai.com/" title="fanhaobai" target="_blank">fanhaobai</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://yuanxuxu.com/archives/" title="yuanxuxu" target="_blank">yuanxuxu</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.snail-c.cn/article" title="snail-c" target="_blank">snail-c</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://showcj.com/archives" title="showcj" target="_blank">showcj</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://vultr.aicnm.com/%E6%9C%80%E6%96%B0Vultr%E6%B3%A8%E5%86%8C%E5%8F%8AVPS%E8%B4%AD%E4%B9%B0%E5%9B%BE%E6%96%87%E6%95%99%E7%A8%8B/" title="vultr" target="_blank">vultr</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.lucissfer.com/" title="lucissfer" target="_blank">lucissfer</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://blog.csdn.net/fdipzone/article/details/79352685" title="傲雪星枫" target="_blank">傲雪星枫</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.yoby123.cn/index.php/category/default/" title="小白的分享" target="_blank">小白的分享</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.cnblogs.com/52fhy/p/5819995.html" title="PHP攻城狮" target="_blank">PHP攻城狮</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://blog.jiaojie.site/" title="php" target="_blank">php</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://sphard.com/archives/" title="sphard" target="_blank">sphard</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://yuanxuxu.com/archives/" title="LNMP技术栈笔记" target="_blank">LNMP技术栈笔记</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://www.coding10.com/" title="学习 Laravel" target="_blank">学习 Laravel</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://shuwoom.com/?page_id=929" title="区块链学习指南" target="_blank">区块链学习指南</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://greenlightt.github.io/archives/" title="greenlightt" target="_blank">greenlightt</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.0php.net/archives/" title="0php" target="_blank">0php</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://www.fordba.com/category/mysql" title="mysql" target="_blank">mysql</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.itcodemonkey.com/" title="程序员" target="_blank">程序员</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.yanshuo.me/r/v2ex" title="言说" target="_blank">言说</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.timiguo.com/archive.html" title="提米果的博客" target="_blank">提米果的博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://phpartisan.cn/news/112.html" title="phpartisan" target="_blank">phpartisan</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.cnblogs.com/52fhy/" title="飞鸿影" target="_blank">飞鸿影</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://www.54php.cn/" title="54php" target="_blank">54php</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.lazyman.vip/" title="营销" target="_blank">营销</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.njphper.com/archives/" title="做人呢最重要的就是开心" target="_blank">做人呢最重要的就是开心</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.h57.pw/" title="php 初心者" target="_blank">php 初心者</a>
                  </li>
                
              </ul>
            </div>
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找（数组里查找某个元素）"><span class="nav-number">1.</span> <span class="nav-text">二分查找（数组里查找某个元素）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#顺序查找（数组里查找某个元素）"><span class="nav-number">2.</span> <span class="nav-text">顺序查找（数组里查找某个元素）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线性表的删除（数组中实现）"><span class="nav-number">3.</span> <span class="nav-text">线性表的删除（数组中实现）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#冒泡排序（数组排序）"><span class="nav-number">4.</span> <span class="nav-text">冒泡排序（数组排序）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序（数组排序）"><span class="nav-number">5.</span> <span class="nav-text">快速排序（数组排序）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串长度"><span class="nav-number">6.</span> <span class="nav-text">字符串长度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#截取子串"><span class="nav-number">7.</span> <span class="nav-text">截取子串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串翻转"><span class="nav-number">8.</span> <span class="nav-text">字符串翻转</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串比较"><span class="nav-number">9.</span> <span class="nav-text">字符串比较</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#查找字符串"><span class="nav-number">10.</span> <span class="nav-text">查找字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串替换"><span class="nav-number">11.</span> <span class="nav-text">字符串替换</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#自实现字符串处理函数"><span class="nav-number">12.</span> <span class="nav-text">自实现字符串处理函数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#删除一段字符串"><span class="nav-number">13.</span> <span class="nav-text">删除一段字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复制字符串"><span class="nav-number">14.</span> <span class="nav-text">复制字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#连接字符串"><span class="nav-number">15.</span> <span class="nav-text">连接字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#简单编码函数（与php-decode函数对应）"><span class="nav-number">16.</span> <span class="nav-text">简单编码函数（与php_decode函数对应）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#简单解码函数（与php-encode函数对应）"><span class="nav-number">17.</span> <span class="nav-text">简单解码函数（与php_encode函数对应）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#简单加密函数（与php-decrypt函数对应）"><span class="nav-number">18.</span> <span class="nav-text">简单加密函数（与php_decrypt函数对应）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#简单解密函数（与php-encrypt函数对应）"><span class="nav-number">19.</span> <span class="nav-text">简单解密函数（与php_encrypt函数对应）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#王者编程大赛之四-—-约瑟夫环"><span class="nav-number">20.</span> <span class="nav-text">王者编程大赛之四 — 约瑟夫环</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#阶梯式电费算法"><span class="nav-number">21.</span> <span class="nav-text">阶梯式电费算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#按照奖品概率分布抽奖"><span class="nav-number">22.</span> <span class="nav-text">按照奖品概率分布抽奖</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#非负元素数组所有元素能组合的最大字符串"><span class="nav-number">23.</span> <span class="nav-text">非负元素数组所有元素能组合的最大字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#PHP生成随机红包算法"><span class="nav-number">24.</span> <span class="nav-text">PHP生成随机红包算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#复杂度"><span class="nav-number">25.</span> <span class="nav-text">复杂度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序"><span class="nav-number">26.</span> <span class="nav-text">快速排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#雪花算法"><span class="nav-number">27.</span> <span class="nav-text">雪花算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#时间复杂度"><span class="nav-number">28.</span> <span class="nav-text">时间复杂度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#排序"><span class="nav-number">29.</span> <span class="nav-text">排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#两数之和"><span class="nav-number">30.</span> <span class="nav-text">两数之和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#索引顺序查找"><span class="nav-number">31.</span> <span class="nav-text">索引顺序查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数据结构栈和队列排队算法"><span class="nav-number">32.</span> <span class="nav-text">数据结构栈和队列排队算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#队列数据结构"><span class="nav-number">33.</span> <span class="nav-text">队列数据结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找"><span class="nav-number">34.</span> <span class="nav-text">二分查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#约瑟夫环"><span class="nav-number">35.</span> <span class="nav-text">约瑟夫环</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#TwoSum"><span class="nav-number">36.</span> <span class="nav-text">TwoSum</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找-1"><span class="nav-number">37.</span> <span class="nav-text">二分查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找法"><span class="nav-number">38.</span> <span class="nav-text">二分查找法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#对称括号"><span class="nav-number">39.</span> <span class="nav-text">对称括号</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#无限级菜单"><span class="nav-number">40.</span> <span class="nav-text">无限级菜单</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<div class="copyright">&copy; <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">苏生不惑</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>



<div>
<span id="showDays"></span>

</div>

<span id="busuanzi_container_site_pv">
   总访问量:<span id="busuanzi_value_site_pv"></span>次
</span>



  <span class="post-meta-divider">|</span>



<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">博客全站共773.8k字</span>
</div>
<script>
var birthDay = new Date("11/20/2018");
var now = new Date();
var duration = now.getTime() - birthDay.getTime();
var total= Math.floor(duration / (1000 * 60 * 60 * 24));
document.getElementById("showDays").innerHTML = "本站已运行 "+total+" 天";
</script>

        
<div class="busuanzi-count">
  <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      人次
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      次
    </span>
  
</div>








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  


  











  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  

  
  
    <script type="text/javascript" src="/lib/canvas-nest/canvas-nest.min.js"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  











<script type="text/javascript">
    (function() {
        // 匿名函数，防止污染全局变量
        var utterances = document.createElement('script');
        utterances.type = 'text/javascript';
        utterances.async = true;
        utterances.setAttribute('issue-term','0')
        utterances.setAttribute('theme','')
        utterances.setAttribute('repo','sushengbuhuo/laravel_ioc_demo')
        utterances.crossorigin = 'anonymous';
        utterances.src = 'https://utteranc.es/client.js';
        // content 是要插入评论的地方
        document.getElementById('gitment-container').appendChild(utterances);
    })();
</script>


  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

  
<script>
  ((window.gitter = {}).chat = {}).options = {
    //room替换成自己的聊天室名称即可，room的名称规则是：username/roomname
    room: 'sushengbuhuo-chat/mychat'
  };
</script>
<script src="https://sidecar.gitter.im/dist/sidecar.v1.js" async defer></script>

</body>
</html>
